algoadvance

Leetcode 2331. Evaluate Boolean Binary Tree

Problem Statement

Given the root of a full binary tree, you need to evaluate the value of this binary tree. In a full binary tree, each node has either 0 or 2 children. Leaves (nodes with 0 children) have either the value 0 or 1. Non-leaf nodes have either the value 2 representing a logical OR, or the value 3 representing a logical AND.

The evaluation of the tree is defined as follows:

• A leaf node evaluates to its value, either 0 or 1.
• A non-leaf node with value 2 represents a logical OR and evaluates to the logical OR of its two children.
• A non-leaf node with value 3 represents a logical AND and evaluates to the logical AND of its two children.

Return the Boolean result of evaluating the root node.

Clarifying Questions

1. What type of TreeNode structure should we use?
   • Assume a TreeNode class is provided with the following definition:

     class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }
     

2. What kind of result should be returned?
   • Return a boolean result indicating the value of the evaluated binary tree.
3. How should the logical operators work?
   • For OR (node value 2), if either of the child nodes evaluates to true, the node evaluates to true.
   • For AND (node value 3), both child nodes must evaluate to true for the node to evaluate to true.

Strategy

1. Base Case (Leaf Evaluation):
   • If a node has no children (leaf), return its value converted to a boolean (0 to false, 1 to true).
2. Recursive Case (Non-leaf Evaluation):
   • Recursively evaluate both the left and right children.
   • Apply the logical operator based on the node’s value (2 for OR, 3 for AND).

Code

public class Solution {
    public boolean evaluateTree(TreeNode root) {
        return evaluate(root);
    }

    private boolean evaluate(TreeNode node) {
        // Base case: if it is a leaf node
        if (node.left == null && node.right == null) {
            return node.val == 1;
        }
        
        // Recursively evaluate left and right children
        boolean leftVal = evaluate(node.left);
        boolean rightVal = evaluate(node.right);
        
        // Non-leaf node values: 2 for OR, 3 for AND
        if (node.val == 2) {
            return leftVal || rightVal;
        } else if (node.val == 3) {
            return leftVal && rightVal;
        }
        
        // For completeness, although we'll never end up here due to problem constraints
        return false;
    }
}

Time Complexity

The time complexity of the solution is O(n), where n is the number of nodes in the tree.

• We’re visiting each node exactly once to evaluate it.
• The recursion ensures that both subtrees of every node are visited.

Thus, the solution efficiently evaluates the binary tree using depth-first search.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?