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 <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11bool evaluateTree(TreeNode* root) {
12 if (!root->left && !root->right)
13 return root->val;
14 bool left = evaluateTree(root->left);
15 bool right = evaluateTree(root->right);
16 return root->val == 2 ? left || right : left && right;
17}The C++ solution leverages the same recursive strategy as the C code. The evaluateTree function recursively checks whether a given TreeNode is a leaf and computes the evaluation based on the logical operators 'OR' or 'AND' for non-leaf nodes.
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
JavaScript shows an iterative depth-first technique utilizing an object-structured stack to handle nodes and indicators successively, refocusing to each processing layer when necessary to apply logical operations.