- a dfs recursive traversal if the current node is nullptr
- return *something* go up the call stack to the leaf node
- check the left and right child true / false values and compute the boolean value based on the current nodes AND/OR value
- return the result up the call stack
- keep going until we have traversd the tree
🤔What Did I Struggle With?
~ should stop at the leaf node rather than recursively reaching a nullptr node
💡 Explanation of Solution
Recursive DFS:
- Start at the root of the tree.
- For each node, recursively evaluate its left and right children.
Base Case:
- If the current node is a leaf node (i.e., both children are `nullptr`), return the value of the node itself (either `true` or `false`).
Recursive Case:
- If the current node is an operator (`AND` or `OR`), recursively evaluate its left and right subtrees to get their boolean values.
- Compute the result based on the operator:
- If the node represents `OR` (value `2`), return `left OR right`.
- If the node represents `AND` (value `3`), return `left AND right`.
Continue Up the Call Stack:
- Return the computed boolean value to the parent node until the entire tree is evaluated.
⌛ Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
💻 Implementation of Solution
class Solution {public: bool evaluateTree(TreeNode* root) { // Base case: If the node is a leaf, return its value if (root->left == nullptr && root->right == nullptr) { return root->val; // Leaf node (0 or 1 represents false or true) } // Recursive case: Evaluate left and right subtrees bool left = evaluateTree(root->left); bool right = evaluateTree(root->right); // Compute the result based on the operator if (root->val == 2) { // OR operator return left || right; } else if (root->val == 3) { // AND operator return left && right; } // Default case (should never occur in a valid input) return false; }};