algoadvance

Leetcode 2331. Evaluate Boolean Binary Tree

Problem Statement

You are given the root of a full binary tree with the following properties:

• Leaf nodes have either the value 0 or 1, representing False and True respectively.
• Non-leaf nodes have either the value 2 or 3:
  • Node with value 2 represents the boolean OR operation.
  • Node with value 3 represents the boolean AND operation.

Return the boolean result of the evaluation of the binary tree.

Example:

Input: root = [2,1,3,null,null,0,1]
Output: true
Explanation: The above diagram represents the binary tree:
        2
       / \
      1   3
         / \
        0   1
 The evaluation of this tree would be True OR (False AND True), which is True.

Clarifying Questions

1. Can the tree have only one node?
   • Yes, it can be a single leaf node, which can either be 0 or 1.
2. Are all trees guaranteed to be valid full binary trees?
   • Yes, the tree is guaranteed to be a full binary tree.

Strategy

To solve this problem, we will perform a post-order traversal of the tree. Post-order traversal is suitable because we need to evaluate the children before we can evaluate the parent. Here is a step-by-step plan:

1. Define a helper function to evaluate the tree recursively.
2. For a leaf node, simply return its boolean value.
3. For non-leaf nodes, recursively evaluate the left and right subtrees.
4. Depending on the value of the non-leaf node (2 for OR and 3 for AND), combine the results of the left and right subtrees using the corresponding boolean operation.

Code

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        // Base case for leaf node
        if (root->left == nullptr && root->right == nullptr) {
            return root->val == 1;
        }
        
        // Recursively evaluate left and right subtrees
        bool leftVal = evaluateTree(root->left);
        bool rightVal = evaluateTree(root->right);
        
        // Perform the operation based on the value of the node
        if (root->val == 2) {
            return leftVal || rightVal;
        } else { // root->val must be 3
            return leftVal && rightVal;
        }
    }
};

Time Complexity

• Time Complexity: The time complexity is (O(N)), where (N) is the number of nodes in the binary tree. This is because we visit each node exactly once.
• Space Complexity: The space complexity is (O(H)), where (H) is the height of the tree. This is due to the recursion stack used for the tree traversal. In the worst case, for a tree that is a chain, (H = N). For a balanced tree, (H = \log(N)).

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?