Evaluate Boolean Binary Tree

class Solution {
public:
    bool evaluateTree(TreeNode* node) {
        stack<TreeNode*> nodeStack;
        nodeStack.push(node);
        unordered_map<TreeNode*, bool> results;

        while (!nodeStack.empty()) {
            TreeNode* currentNode = nodeStack.top();

            if (!currentNode->left && !currentNode->right) {
                nodeStack.pop();
                results[currentNode] = currentNode->val;
                continue;
            }

            if (results.find(currentNode->left) != results.end() &&
                results.find(currentNode->right) != results.end()) {
                nodeStack.pop();
                if (currentNode->val == 2) {
                    results[currentNode] =
                        results[currentNode->left] || results[currentNode->right];
                } else {
                    results[currentNode] =
                        results[currentNode->left] && results[currentNode->right];
                }
            } else {
                if (currentNode->left) nodeStack.push(currentNode->left);
                if (currentNode->right) nodeStack.push(currentNode->right);
            }
        }

        return results[node] == 1;
    }
};

This solution evaluates a binary tree to determine the truth value of expressions represented by the nodes. In this tree, leaf nodes denote boolean values, and internal nodes denote boolean operations (AND represented by '1', OR by '2'). The code uses the C++ language.

Detailed Breakdown:

1. The evaluateTree function uses a stack (nodeStack) to traverse nodes in the tree and an unordered map (results) to store evaluation results of the nodes.

2. The traversal begins from the root node, adding it to the stack. The code then enters a while loop that processes nodes until the stack is empty.

3. Inside the loop:

   • The top node from the stack (currentNode) is examined.
   • If currentNode is a leaf node (both left and right children are null), its boolean value (currentNode->val) is directly stored in the results map, and the node is removed from the stack.
   • If currentNode is an internal node:
     • Once both its children are evaluated and present in the results map, it calculates the logical operation based on the type of the node (currentNode->val):
       • For '2' (OR operation), combine the results of left and right children using logical OR.
       • For '1' (AND operation), combine them using logical AND.
     • The combined result is stored back in the results map.
   • If the current node's children are not yet processed, they are added to the stack for subsequent evaluation.

4. At the end of the loop, the function returns the evaluation result of the root node by checking if results[node] == 1.

• This approach effectively mimics a post-order traversal using a manual stack to manage tree nodes, ensuring that child nodes are processed before their parent nodes, which is crucial for evaluating the expressions represented by the tree.

class Solution {
    public boolean evaluateTree(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        HashMap<TreeNode, Boolean> values = new HashMap<>();

        while (!stack.isEmpty()) {
            TreeNode currentNode = stack.peek();
            if (currentNode.left == null && currentNode.right == null) {
                stack.pop();
                values.put(currentNode, currentNode.val == 1);
                continue;
            }

            if (values.containsKey(currentNode.left) && values.containsKey(currentNode.right)) {
                stack.pop();
                if (currentNode.val == 2) {
                    values.put(currentNode, values.get(currentNode.left) || values.get(currentNode.right));
                } else {
                    values.put(currentNode, values.get(currentNode.left) && values.get(currentNode.right));
                }
            } else {
                if (currentNode.right != null) {
                    stack.push(currentNode.right);
                }
                if (currentNode.left != null) {
                    stack.push(currentNode.left);
                }
            }
        }
        
        return values.get(node);
    }
}

The provided Java solution implements a method to evaluate a boolean binary tree, where each leaf node represents a boolean value (0 for false, 1 for true), and the internal nodes represent logical operations (AND represented by 3, OR by 2). The method uses a depth-first search approach utilizing a stack to traverse the tree and a hashmap to store the evaluated values of the nodes.

• The method evaluateTree(TreeNode node) defines the root of the tree with which the evaluation starts.
• A Stack<TreeNode> is initiated to manage the nodes during tree traversal and a HashMap<TreeNode, Boolean> to store the truth values of nodes.
• Within a loop, nodes are popped from the stack, evaluated based on their type (operator or operand), and their resultant values are stored in the hashmap.
• For internal nodes (nodes representing AND or OR), results from their left and right children are fetched from the hashmap, and the boolean operation respective to the value of the current node is applied.
• The loop continues until all nodes are evaluated, and the final boolean result stored in the hashmap for the root node is returned.

This depth-first evaluation avoids recursion and effectively calculates the boolean result for a binary tree representing a logical expression, making it a robust solution for such types of problems.

class Solution:
    def processNode(self, node: Optional[TreeNode]) -> bool:
        nodes = [node]
        results = {}
        
        while nodes:
            current = nodes[-1]
            
            if not current.left and not current.right:
                nodes.pop()
                results[current] = current.val == 1
                continue
            
            if current.left in results and current.right in results:
                nodes.pop()
                if current.val == 2:
                    results[current] = results[current.left] or results[current.right]
                else:
                    results[current] = results[current.left] and results[current.right]
            else:
                if current.left:
                    nodes.append(current.left)
                if current.right:
                    nodes.append(current.right)
        
        return results[node]

The given Python code defines a method processNode within the Solution class, which evaluates a boolean binary tree based on certain logical operations represented by the node values. The tree nodes can represent either boolean values (True or False, depicted as 1 or 0) or boolean operators (AND and OR, depicted as 3 and 2 correspondingly).

The approach employs a depth-first search (DFS) strategy with the help of a list nodes that acts as a stack to store nodes to be processed. A dictionary results is used to map each node to its computed boolean value.

• Key steps in the code include:

  1. Initializing the stack with the root node and an empty dictionary for storing results.
  2. Iterating until there are no nodes left in the stack.
  3. Checking if the current node is a leaf by verifying it has no children; the result for this node is directly assigned based on its value.
  4. Determining the result for non-leaf nodes by checking if the results for both child nodes are already computed:
     • For nodes with value 2 (OR operation), the result is the logical OR of both children's results.
     • For nodes with value 3 (AND operation), the result is the logical AND of both children's results.
  5. If results of child nodes are not computed yet, children nodes are added to the stack for further processing.

• The method finally returns the computed result of the root node.

This structure makes the function robust and efficient for evaluating trees representing complex boolean expressions. The use of depth-first logic ensures that all nodes are processed in the correct order, achieving appropriate boolean evaluation based on the pre-defined logical rules in the tree structure.