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
This C solution uses a custom stack to simulate the recursion explicitly. Each node is processed with flags indicating the state of child evaluations, generating results from processed children before combining them under logical operations by parent nodes.