2331.evaluate-boolean-binary-tree.md

2331. Evaluate Boolean Binary Tree

Postorder Traversal

We have to evaluate the boolean expression in bottom-up manner, so we can use postorder traversal to solve this problem.

fun evaluateTree(root: TreeNode?): Boolean {
    if (root == null) return true
    if (root.left == null && root.right == null) {
        return root.`val` == 1
    }
    val left = evaluateTree(root.left)
    val right = evaluateTree(root.right)

    if (root.`val` == 3) {
        return left && right
    } else {
        return left || right
    }
}

• Time Complexity: O(n).
• Space Complexity: O(h).