Evaluate Boolean Binary Tree Python Solution

Tested Python solution for LeetCode 2331 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 2331, Easy. Topics: Tree, Depth-First Search, Binary Tree. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 21 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2331   # by problem number
lcpy gen -s evaluate_boolean_binary_tree   # by problem name

​

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.

The evaluation of a node is as follows:

• If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
• Otherwise, evaluate the node’s two children and apply the boolean operation of its value with the children’s evaluations.

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.

​

Examples

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.

Input: root = [0]
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.

​

Constraints

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 3
• Every node has either 0 or 2 children.
• Leaf nodes have a value of 0 or 1.
• Non-leaf nodes have a value of 2 or 3.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(h)
    def evaluate_tree(self, root: TreeNode[int] | None) -> bool:
        if root is None:
            return False
        if root.left is None and root.right is None:
            return root.val == 1
        left = self.evaluate_tree(root.left)
        right = self.evaluate_tree(root.right)
        return (left or right) if root.val == 2 else (left and right)

​

Complexity

Time	Space
O(n)	O(h)

​

Tags

NeetCode All.