LeetCode 988: Smallest String Starting From Leaf Solution

Master LeetCode problem 988 (Smallest String Starting From Leaf), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

988. Smallest String Starting From Leaf

Medium

String Backtracking Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To find the lexicographically smallest string starting from a leaf node and ending at the root in a binary tree, we can perform a depth-first search (DFS) traversal from each leaf node to the root while constructing the string. We will compare the current path string with the smallest string found so far and update it if the current path is lexicographically smaller.

Perform a DFS traversal from each leaf node to the root, constructing the path string as we go.
At each node, append the character corresponding to the current node's value to the path string.
Compare the path string with the current smallest string found so far. If the path string is lexicographically smaller, update the smallest string.
Continue the DFS traversal until reaching the root node.
Return the final smallest string found.

Time Complexity: O(n), where n is the number of nodes in the binary tree. Space Complexity: O(h), where h is the height of the binary tree.

Solution Code

class Solution {
    String smallest = "~";

    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder());
        return smallest;
    }

    private void dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;

        path.append((char) ('a' + node.val));

        if (node.left == null && node.right == null) {
            path.reverse();
            String currentString = path.toString();
            path.reverse();

            if (currentString.compareTo(smallest) < 0) {
                smallest = currentString;
            }
        }

        dfs(node.left, path);
        dfs(node.right, path);

        path.deleteCharAt(path.length() - 1);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 988 (Smallest String Starting From Leaf)?

This page provides optimized solutions for LeetCode problem 988 (Smallest String Starting From Leaf) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 988 (Smallest String Starting From Leaf)?

The time complexity for LeetCode 988 (Smallest String Starting From Leaf) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 988 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 988 in Java, C++, or Python.

Back to LeetCode Solutions