#10EasyTrees· Post-order Evaluation

Evaluate Boolean Binary Tree

A **full** binary tree (every node has either zero or two children) encodes a boolean expression: - a leaf holds `0` (false) or `1` (true), - an internal node holds `2` (OR) or `3` (AND) and applies that operator to the values of its two children. Return the boolean result of evaluating the tree at its `root`. The tree is given as a level-order array: values are listed breadth-first, left to right, and `null` marks a missing child. Children of a missing node are not listed.

Input format

root: level-order array of integers in {0, 1, 2, 3} with `null` for missing children

Output format

Boolean: the value of the expression

Examples

Input: root = [2, 1, 3, null, null, 0, 1]

Output: true

The right subtree is AND(0, 1) = false; the root is OR(true, false) = true.

Input: root = [0]

Output: false

A single leaf with value 0 is false.

Input: root = [3, 3, 2, 1, 1, 0, 0]

Output: false

The left subtree is AND(1, 1) = true, the right is OR(0, 0) = false, and AND(true, false) = false.

Constraints

1 <= number of nodes <= 1000
Leaves have value 0 or 1; internal nodes have value 2 or 3.
Every internal node has exactly two children.

Study first

#trees
#depth-first-search
#recursion
#boolean-logic