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
This C solution uses a custom stack to simulate the recursion explicitly. Each node is processed with flags indicating the state of child evaluations, generating results from processed children before combining them under logical operations by parent nodes.