The Indian Engineer

Problem 2331 Evaluate Boolean Binary Tree

Posted on 3 mins

Binary-Tree Dfs Bit-Manipulation Cpp

Table of Contents

Problem Statement

Link - Problem 2331

Question

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

The evaluation of a node is as follows:

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.

Example 1

Input

graph TD A((2))-->B((1)) A-->C((3)) C((3))-->D((0)) C((3))-->E((1)) F((OR))-->G((True)) F-->H((AND)) H-->I((False)) H-->J((True)) 

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.

Example 2 

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

Constraints

Solution 

/**
 * 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) {
        if(root->left == nullptr && root->right == nullptr)
            return root->val;

        else
        {
            if(root->val == 2)
                return evaluateTree(root->left) || evaluateTree(root->right);
            else
                return  evaluateTree(root->left) && evaluateTree(root->right);
        }

    }
};

Complexity Analysis

Explanation

1. Intuition

2. Implementation