# 16.05.2024 [2331. Evaluate Boolean Binary Tree]

Evaluate tree where `0/1` is `false/true` and `2/3` is `or/and` #easy #tree #dfs

16.05.2024

2331. Evaluate Boolean Binary Tree easy
blog post

youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/604

Problem TLDR

Evaluate tree where 0/1 is false/true and 2/3 is or/and #easy #tree #dfs

Intuition

We can solve a subproblem for each node in a recursion.

Approach

Let’s try to avoid the double walk by changing the boolean operations order.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(log(n)) for the recursion depth

Code

    fun evaluateTree(root: TreeNode?): Boolean = root?.run {
    if (`val` < 1) false else `val` < 2
    || evaluateTree(left) && (`val` < 3 || evaluateTree(right))
    || `val` < 3 && evaluateTree(right) } ?: false

    pub fn evaluate_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        root.as_ref().map_or(false, |n| { let mut n = n.borrow_mut();
            if n.val < 1 { false } else {
            n.val < 2 || Self::evaluate_tree(n.left.take()) 
            && (n.val < 3 || Self::evaluate_tree(n.right.take()))
            || n.val < 3 && Self::evaluate_tree(n.right.take())
        }})
    }