2331. Evaluate Boolean Binary Tree

Problem Description

In this problem, we're given the root of a full binary tree representing a boolean expression. This tree has two types of nodes: leaf nodes and non-leaf nodes. Leaf nodes can only have a value of 0 (representing False) or 1 (representing True). Non-leaf nodes, on the other hand, hold a value of either 2 (representing the OR operation) or 3 (representing the AND operation). The task is to evaluate this tree according to the following rules:

If the node is a leaf, its evaluation is based on its value (True for 1, and False for 0).
For non-leaf nodes, you need to evaluate both of its children and then apply the node's operation (OR for 2, AND for 3) to these evaluations.

The goal is to return the boolean result of this evaluation, starting at the root of the tree.

A full binary tree, by definition, is a binary tree where each node has exactly 0 or 2 children. A leaf node is a node without any children.

Intuition

The solution to this problem lies in recursion, which matches the tree's structural nature. We will perform a post-order traversal to evaluate the tree – this means we first evaluate the child nodes, and then we apply the operation specified by their parent node. Here's how we can think about our approach:

If we reach a leaf node (a node with no children), we return its boolean value (True for 1, False for 0).
If the node is not a leaf, it will have exactly two children because the tree is a full binary tree. We evaluate the left child and the right child first (recursively calling our function).
Once both children are evaluated, we perform either an OR operation if the node's value is 2 or an AND operation if the node's value is 3.
We continue this process, working our way up the tree, until we reach the root.
The result of evaluating the root node gives us the answer to the problem.

This recursive algorithm effectively simulates the process of evaluating a complex boolean expression, starting from the most basic sub-expressions (the leaf nodes) and combining them as specified by the connecting operation nodes.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Solution Approach

The solution is based on a simple recursive tree traversal algorithm. The evaluateTree function is a recursive function that evaluates whether the boolean expression represented by the binary tree is True or False. Let's take a deeper dive into the implementation steps and algorithms used:

Base Case (Leaf Nodes): If we come across a leaf node (which has no children), the evaluateTree function simply returns the boolean equivalent of the node's value. In Python, the boolean value True corresponds to an integer value 1, and False corresponds to 0. Hence, bool(root.val) is sufficient to get the leaf node's boolean value.
Recursive Case (Non-Leaf Nodes): For non-leaf nodes, since the tree is full, it is guaranteed that if a node is not a leaf, it will have both left and right children. We first recursively evaluate the result of the left child self.evaluateTree(root.left) and store this in the variable l. Similarly, we evaluate the result of the right child self.evaluateTree(root.right) and store it in the variable r.
Combining Results: Once we have the boolean evaluations of the left and the right children, we check the value of the current (parent) node:
- If the parent node's value is 2, we perform an OR operation on the results of the children. This is done by l or r in Python.
- If the parent node's value is 3, we perform an AND operation on the results of the children. This is done by l and r in Python.
Termination and Return Value: The entire process recurses until the root node is evaluated. The result of evaluating the root node is then returned as the result of the boolean expression represented by the binary tree.

Here is a breakdown of the method in pseudocode:

1def evaluateTree(node):
2    if node is a leaf:
3        return the boolean value of the leaf
4    else:
5        left_child_result = evaluateTree(node's left child)
6        right_child_result = evaluateTree(node's right child)
7        if node's value is OR:
8            return left_child_result OR right_child_result
9        else if node's value is AND:
10            return left_child_result AND right_child_result

The elegance of the recursive approach is in its direct mapping to the tree structure and the natural way it processes nodes according to the rules of boolean logic expression evaluation. At the end of the recursive calls, the evaluateTree function gives us the final boolean evaluation for the entire tree starting from the root node. This aligns perfectly with the expected solution for the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Example Walkthrough

Let's walk through an example to illustrate how the solution approach works.

Imagine a small binary tree representing a boolean expression, where leaf nodes are either 0 (False) or 1 (True), and non-leaf nodes are 2 (OR) or 3 (AND). Here is the structure of our example tree:

1        2
2       / \
3      1   3
4         / \
5        0   1

This tree represents the boolean expression (True OR (False AND True)).

Now, let's step through the algorithm:

We start at the root node, which is not a leaf and has a value of 2, representing the OR operation. Since this is not a leaf node, we need to evaluate its children.
We evaluate the left child first. Here, the left child is a leaf with a value of 1 (True). According to our base case, we return True for this node.
Next, we evaluate the right child, which is a non-leaf and has a value of 3, representing the AND operation. Since this is not a leaf node, we need to evaluate its children.
We evaluate the left child of the AND node, which is a leaf with a value of 0 (False). As per our base case, we return False for this node.
Moving to the right child of the AND node, we find it is a leaf with a value of 1 (True). We return True for this leaf.
Now that we have the results of both children of the AND node (False and True), we apply the AND operation. False AND True results in False.
Returning back to the root of the tree, we now have results from both children - True from the left and False from the right (from the AND operation). The root is an OR node, so we apply the OR operation to these results.
True OR False gives us True. So, the final result of evaluating the entire tree is True.

Hence, the boolean expression represented by the binary tree evaluates to True. The recursive approach allowed us to break down the complex expression into simple operations that we could easily evaluate.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7      
8class Solution:
9    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
10        """
11        Evaluates the boolean value of a binary tree where leaves are 0 (False) or 1 (True),
12        and internal nodes are either 2 (OR) or 3 (AND).
13      
14        :param root: The root node of the binary tree.
15        :return: The boolean result of evaluating the binary tree.
16        """
17        # If the current node is a leaf, return the boolean equivalent of its value
18        if root.left is None and root.right is None:
19            return bool(root.val)
20      
21        # Recursively evaluate the left subtree
22        left_value = self.evaluateTree(root.left)
23        # Recursively evaluate the right subtree
24        right_value = self.evaluateTree(root.right)
25      
26        # If the current node's value is 2, perform an OR operation; otherwise, perform an AND operation
27        if root.val == 2:
28            return left_value or right_value
29        else:
30            return left_value and right_value
31

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val; // The value of the node
6    TreeNode left; // Reference to the left child
7    TreeNode right; // Reference to the right child
8
9    // Constructors
10    TreeNode() {}
11    TreeNode(int val) { this.val = val; }
12    TreeNode(int val, TreeNode left, TreeNode right) {
13        this.val = val;
14        this.left = left;
15        this.right = right;
16    }
17}
18
19class Solution {
20    /**
21     * Evaluates the boolean value of a binary tree with nodes labeled either
22     * 0 (false), 1 (true), 2 (OR), or 3 (AND). Leaves of the tree will always
23     * be labeled with 0 or 1. Nodes with values 2 or 3 represent the logical OR
24     * and AND operations, respectively.
25     *
26     * @param root The root node of the binary tree.
27     * @return The boolean result of evaluating the binary tree.
28     */
29    public boolean evaluateTree(TreeNode root) {
30        // Base case: If the node has no children, return true if it's value is 1, false otherwise.
31        if (root.left == null && root.right == null) {
32            return root.val == 1;
33        }
34
35        // Recursively evaluate the left and right subtrees.
36        boolean leftEvaluation = evaluateTree(root.left);
37        boolean rightEvaluation = evaluateTree(root.right);
38
39        // Determine the value of the current expression based on the current node's value
40        // If the node value is 2, perform logical OR, otherwise logical AND (as per the problem, value will be 3).
41        return (root.val == 2) ? leftEvaluation || rightEvaluation : leftEvaluation && rightEvaluation;
42    }
43}
44

1// Definition for a binary tree node.
2struct TreeNode {
3    int val;               // Value of the node
4    TreeNode *left;        // Pointer to the left child
5    TreeNode *right;       // Pointer to the right child
6    // Constructor to initialize a node with no children
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    // Constructor to initialize a node with a specific value and no children
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    // Constructor to initialize a node with a specific value and specified children
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Function to evaluate the value of a boolean binary tree
17    // based on the value of the root (0, 1, and 2 corresponding to false, true, and OR/AND operations)
18    bool evaluateTree(TreeNode* root) {
19        // If the root does not have a left child, it must be a leaf node (value 0 or 1)
20        if (!root->left) {
21            return root->val; // Return the value of the leaf node as the result
22        }
23        // Recursively evaluate the left subtree
24        bool leftResult = evaluateTree(root->left);
25        // Recursively evaluate the right subtree
26        bool rightResult = evaluateTree(root->right);
27        // If the root's value is 2, we perform an OR operation; otherwise, we perform an AND operation
28        return root->val == 2 ? (leftResult || rightResult) : (leftResult && rightResult);
29    }
30};
31

1// Definition for a binary tree node.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8/**
9 * Evaluates the boolean value of a binary logic tree where leaves represent
10 * boolean values and other nodes represent logical operators.
11 *
12 * @param {TreeNode | null} node - A node in a binary tree.
13 * @return {boolean} - The evaluated boolean value of the tree.
14 */
15function evaluateTree(node: TreeNode | null): boolean {
16  // Check if the node is null, which should not happen in a valid call
17  if (!node) {
18    throw new Error('Invalid node: Node cannot be null');
19  }
20
21  // If the node is a leaf node (i.e., both children are null), return true if it's value is 1, else false
22  if (node.left === null && node.right === null) {
23    return node.val === 1;
24  }
25
26  // Check the value of the node to determine the logical operator
27  if (node.val === 2) {
28    // Logical OR operator
29    return evaluateTree(node.left as TreeNode) || evaluateTree(node.right as TreeNode);
30  } else if (node.val === 3) {
31    // Logical AND operator
32    return evaluateTree(node.left as TreeNode) && evaluateTree(node.right as TreeNode);
33  }
34
35  throw new Error('Invalid node value: Node value must be either 1, 2, or 3');
36}
37
38// Note: The code assumes that the tree is a full binary tree and all non-leaf nodes have both left and right children.
39// It also assumes that the leaf nodes have the value 1 (true) or 0 (false), while other nodes have the value 2 (OR) or 3 (AND).
40

Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the binary tree. This is because the function evaluateTree visits each node exactly once to perform the evaluation.

The space complexity is O(h), where h is the height of the binary tree. This space is used by the call stack due to recursion. In the worst case of a skewed tree, where the tree is essentially a linked list, the height h is n, making the space complexity O(n). In the best case, with a balanced tree, the height h would be log(n), resulting in a space complexity of O(log(n)).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2331. Evaluate Boolean Binary Tree

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings