LeetCode Entry

1038. Binary Search Tree to Greater Sum Tree

25.06.2024 medium 2024 kotlin rust

Aggregate Binary Search Tree from the right

1038. Binary Search Tree to Greater Sum Tree medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/650

Problem TLDR

Aggregate Binary Search Tree from the right #medium #tree

Intuition

Just iterate from the tail in an inorder DFS traversal.

Approach

• notice how 26 jumps straight to the root, so we must store the result somewhere
• there is a nice patter in Rust: `let Some(..) = .. else { .. }

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(log(n))\) for the call stack, however, it can be O(1) for the Morris Traversal

Code

    var s = 0
    fun bstToGst(root: TreeNode?): TreeNode? = root?.apply {
        bstToGst(right); `val` += s; s = `val`; bstToGst(left)
    }

    pub fn bst_to_gst(mut root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, s: i32) -> i32 {
            let Some(n) = n.as_ref() else { return s }; let mut n = n.borrow_mut();
            n.val += dfs(&n.right, s); dfs(&n.left, n.val)
        }
        dfs(&root, 0); root
    }