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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var evaluateTree = function(root) {
8 if (!root.left && !root.right)
9 return root.val === 1;
10 let left = evaluateTree(root.left);
11 let right = evaluateTree(root.right);
12 return root.val === 2 ? left || right : left && right;
13};Javascript code makes use of recursion to evaluate the tree, examining leaf and non-leaf nodes for computing boolean logic operations, following a depth-first traversal method.
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.