Evaluate Boolean Binary Tree - Practice Coding Problems

Evaluate Boolean Binary Tree - 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.

Input & Output

Example 1 — OR with Mixed Children

$ Input: root = [2,1,3,null,null,0,1]

› Output: true

💡 Note: Leaf nodes: 1→True, 0→False, 1→True. Right subtree: 0 AND 1 = False. Root: 1 OR False = True

Example 2 — Simple OR Operation

$ Input: root = [2,0,1]

› Output: true

💡 Note: Root has OR operation with children 0 (False) and 1 (True). False OR True = True

Example 3 — Simple AND Operation

$ Input: root = [3,1,0]

› Output: false

💡 Note: Root has AND operation with children 1 (True) and 0 (False). True AND False = 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.

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with leaf values 0/1 and operation nodes 2(OR)/3(AND)

Evaluate Bottom-Up

Process leaves first, then apply operations

Final Result

Root node evaluation gives the boolean answer

Key Takeaway

🎯 Key Insight: Use recursion to naturally handle tree structure - evaluate children first, then apply boolean operations

Asked in

a Amazon 15 M Microsoft 12 G Google 8 f Meta 6

The key insight is to use recursion to naturally evaluate the boolean binary tree from leaves to root. For leaf nodes (0 or 1), return the boolean value directly. For operation nodes (2 for OR, 3 for AND), recursively evaluate children and apply the operation. Best approach uses DFS recursion with Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive DFS	O(n)	O(h)	Recursively evaluate each node based on its value and children
Iterative DFS with Stack	O(n)	O(n)	Use explicit stack to avoid recursion overhead

Recursive DFS — Algorithm Steps

Check if current node is a leaf (value 0 or 1)
If leaf, return boolean value directly
If not leaf, recursively evaluate left and right children
Apply OR operation if value is 2, AND operation if value is 3

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Leaves

Find leaf nodes with values 0 or 1

Evaluate Operations

Apply AND/OR operations on children results

Return Result

Root evaluation gives final boolean result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool solution(struct TreeNode* root) {
    if (!root) return false;
    
    // Leaf node: return boolean value
    if (root->val == 0 || root->val == 1) {
        return root->val == 1;
    }
    
    // Non-leaf node: evaluate children and apply operation
    bool leftResult = solution(root->left);
    bool rightResult = solution(root->right);
    
    if (root->val == 2) {  // OR operation
        return leftResult || rightResult;
    } else {  // root->val == 3, AND operation
        return leftResult && rightResult;
    }
}

struct TreeNode* buildTree(int* arr, int size, int index) {
    if (index >= size || arr[index] == -1) {
        return NULL;
    }
    
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = arr[index];
    root->left = buildTree(arr, size, 2 * index + 1);
    root->right = buildTree(arr, size, 2 * index + 2);
    return root;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,] \n");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[,] \n");
    }
    
    struct TreeNode* root = buildTree(arr, size, 0);
    bool result = solution(root);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in the tree

✓ Linear Growth

Space Complexity

O(h)

Recursion call stack depth equals tree height h

✓ Linear Space

95.0K Views

Medium Frequency

~10 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler