You are given the root of a full binary tree with the following properties:
0 or 1, where 0 represents False and 1 represents True.2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.The evaluation of a node is as follows:
True or False.Return the boolean result of evaluating the root node.
A full binary tree is a binary tree where each node has either 0 or 2 children.
A leaf node is a node that has zero children.
Example 1:
Input: root = [2,1,3,null,null,0,1] Output: true Explanation: The above diagram illustrates the evaluation process. The AND node evaluates to False AND True = False. The OR node evaluates to True OR False = True. The root node evaluates to True, so we return true.
Example 2:
Input: root = [0] Output: false Explanation: The root node is a leaf node and it evaluates to false, so we return false.
Constraints:
[1, 1000].0 <= Node.val <= 30 or 2 children.0 or 1.2 or 3.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).
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), as all nodes are processed.
Space Complexity: O(n), given the stack memory employment.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) where n is the number of nodes, since we need to visit each node once. |
| Iterative Approach (Using Stack) | Time Complexity: O(n), as all nodes are processed. |
Evaluate Boolean Binary Tree - Leetcode 2331 - Python • NeetCodeIO • 8,750 views views
Watch 9 more video solutions →Practice Evaluate Boolean Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor