LeetCode Entry

988. Smallest String Starting From Leaf

17.04.2024 medium 2024 kotlin rust

Smallest string from leaf to root in a Binary Tree

988. Smallest String Starting From Leaf medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/574

Problem TLDR

Smallest string from leaf to root in a Binary Tree #medium

Intuition

After trying some examples with bottom-up approach, we find out one that would not work: That means, we should use top down.

Approach

• We can avoid using a global variable, comparing the results.
• The if branching can be smaller if we add some symbol after z for a single-leafs.

Complexity

• Time complexity: \(O(nlog^2(n))\), we prepending to string with length of log(n) log(n) times, can be avoided with StringBuilder and reversing at the last step

• Space complexity: \(O(log(n))\), recursion depth

Code

    fun smallestFromLeaf(root: TreeNode?, s: String = ""): String = root?.run {
        val s = "${'a' + `val`}" + s
        if (left == null && right == null) s
        else minOf(smallestFromLeaf(left, s), smallestFromLeaf(right, s))
    } ?: "${ 'z' + 1 }"

    pub fn smallest_from_leaf(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, s: String) -> String {
            n.as_ref().map_or("{".into(), |n| { let n = n.borrow();
                let s = ((b'a' + (n.val as u8)) as char).to_string() + &s;
                if n.left.is_none() && n.right.is_none() { s }
                else { dfs(&n.left, s.clone()).min(dfs(&n.right, s)) }
            })
        }
        dfs(&root, "".into())
    }