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.
1#include <stdbool.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9bool evaluateTree(struct TreeNode* root) {
10 if (root->val < 2)
11 return root->val;
12 bool left = evaluateTree(root->left);
13 bool right = evaluateTree(root->right);
14 return root->val == 2 ? left || right : left && right;
15}This C function implements the recursive evaluation of the binary tree. It first checks if the node is a leaf. If so, it returns the value directly. If not, it recursively evaluates the left and right subtrees, then applies the appropriate boolean operation ('OR' or 'AND') depending on the 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.