Evaluate Boolean Binary Tree — LeetCode 2331 Python Solution

The problem

You are given the root of a full binary tree with the following properties: Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True. Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.

Example

Input

root = [2,1,3,null,null,0,1]

Output

true

Explanation

The above diagram illustrates the evaluation process.

Python solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if root.left is None:
            return bool(root.val)
        op = or_ if root.val == 2 else and_
        return op(self.evaluateTree(root.left), self.evaluateTree(root.right))

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 2331. Evaluate Boolean Binary Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems