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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public boolean evaluateTree(TreeNode root) {
10 if (root.left == null && root.right == null) {
11 return root.val == 1;
12 }
13 boolean left = evaluateTree(root.left);
14 boolean right = evaluateTree(root.right);
15 return root.val == 2 ? left || right : left && right;
16 }
17}The Java code demonstrates a similar recursive function. It determines whether the TreeNode is a leaf by checking its children and performs recursion accordingly, applying logical 'OR' or 'AND' based on node values.
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
The Python solution opts for iteration via a stack implemented as a list, managing nodes with a tuple indicating processing state. Child node values are processed first before handling parent's logical operation.