Sponsored
Sponsored
This approach uses recursion to evaluate the binary boolean tree. Starting from the root, recursively evaluate the left and right children of each node. If a node is a leaf, return its boolean value. If a node is non-leaf, apply the boolean operation defined by its value on its children's evaluations (OR for 2, AND for 3).
Time Complexity: O(n) where n is the number of nodes, since we need to visit each node once.
Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var evaluateTree = function(root) {
8 if (!root.left && !root.right)
9 return root.val === 1;
10 let left = evaluateTree(root.left);
11 let right = evaluateTree(root.right);
12 return root.val === 2 ? left || right : left && right;
13};Javascript code makes use of recursion to evaluate the tree, examining leaf and non-leaf nodes for computing boolean logic operations, following a depth-first traversal method.
This method employs an iterative approach using a stack to emulate the recursive behavior. By performing a depth-first traversal, it uses a stack to track nodes and their processed children, evaluating each in line with the tree's logic operations.
Time Complexity: O(n), as all nodes are processed.
Space Complexity: O(n), given the stack memory employment.
1
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool EvaluateTree(TreeNode root) {
if (root == null) return false;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
if (node.left == null && node.right == null) {
node.val = node.val == 1 ? 1 : 0;
continue;
}
if (node.left != null) stack.Push(node.left);
if (node.right != null) stack.Push(node.right);
int leftVal = node.left != null ? node.left.val : 0;
int rightVal = node.right != null ? node.right.val : 0;
if (node.val == 2) { // OR
node.val = (leftVal == 1 || rightVal == 1) ? 1 : 0;
} else if (node.val == 3) { // AND
node.val = (leftVal == 1 && rightVal == 1) ? 1 : 0;
}
}
return root.val == 1;
}
}C# employs a procedural stack to navigate node evaluations, storing temporary results atop the stack, and computing parent's value once children have been processed through logical operations.