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 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def evaluateTree(self, root: TreeNode) -> bool:
9 if not root.left and not root.right:
10 return root.val == 1
11 left = self.evaluateTree(root.left)
12 right = self.evaluateTree(root.right)
13 return (left or right) if root.val == 2 else (left and right)Python version follows the recursive evaluation pattern where recursive calls are used for children evaluations and logical operations are applied based on the current node's value.
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.