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
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool EvaluateTree(TreeNode root) {
if (root == null) return false;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
if (node.left == null && node.right == null) {
node.val = node.val == 1 ? 1 : 0;
continue;
}
if (node.left != null) stack.Push(node.left);
if (node.right != null) stack.Push(node.right);
int leftVal = node.left != null ? node.left.val : 0;
int rightVal = node.right != null ? node.right.val : 0;
if (node.val == 2) { // OR
node.val = (leftVal == 1 || rightVal == 1) ? 1 : 0;
} else if (node.val == 3) { // AND
node.val = (leftVal == 1 && rightVal == 1) ? 1 : 0;
}
}
return root.val == 1;
}
}C# employs a procedural stack to navigate node evaluations, storing temporary results atop the stack, and computing parent's value once children have been processed through logical operations.