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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
6 this.val = val;
7 this.left = left;
8 this.right = right;
9 }
10}
11
12public class Solution {
13 public bool EvaluateTree(TreeNode root) {
14 if (root.left == null && root.right == null) {
15 return root.val == 1;
16 }
17 bool left = EvaluateTree(root.left);
18 bool right = EvaluateTree(root.right);
19 return root.val == 2 ? left || right : left && right;
20 }
21}C# implementation is built around a similar recursive idea, with base evaluation of leaf node values and recursion to handle non-leaf nodes' logical operations.
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
In Java, this iterative method uses a stack to perform depth-first traversal, determining each node's evaluation directly or post-child-processing. Logical calculations are performed at each non-leaf node based on stored child results.