LeetCode Entry

2331. Evaluate Boolean Binary Tree

16.05.2024 easy 2024 kotlin rust

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

2331. Evaluate Boolean Binary Tree easy blog post substack 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())
        }})
    }