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
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool evaluateTree(TreeNode* root) {
std::stack<std::pair<TreeNode*, bool>> s;
s.push({root, false});
while (!s.empty()) {
auto [node, processed] = s.top();
s.pop();
if (!node->left && !node->right) {
node->val = node->val == 1;
continue;
}
if (!processed) {
s.push({node, true});
if (node->right) s.push({node->right, false});
if (node->left) s.push({node->left, false});
} else {
bool left = node->left->val;
bool right = node->right->val;
node->val = node->val == 2 ? (left || right) : (left && right);
}
}
return root->val;
}The C++ example adopts an iterative stack-based approach pairing TreeNode pointers with a 'processed' flag for each entry. Nodes are revisited after evaluating children, applying logical operations before combining results back up the stack.