Skip to main content
Talentd

Smallest String Starting From Leaf - Solution & Explanation

MediumStringBacktrackingTreeDepth-First Search10 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.

Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

As a reminder, any shorter prefix of a string is lexicographically smaller.

  • For example, "ab" is lexicographically smaller than "aba".

A leaf of a node is a node that has no children.

 

Example 1:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: root = [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"

 

Constraints:

  • The number of nodes in the tree is in the range [1, 8500].
  • 0 <= Node.val <= 25

Approach Overview

Problem Overview: Each node in the binary tree stores a value from 0–25 representing characters 'a' to 'z'. A valid string is built by starting at a leaf and moving upward to the root. The task is to return the lexicographically smallest such string among all leaf‑to‑root paths.

Approach 1: Generate All Leaf Strings (DFS + Store Paths) (Time: O(n * h), Space: O(n * h))

Run a Depth-First Search from the root and maintain the current path of characters. When a leaf node is reached, reverse the path to convert the root‑to‑leaf order into the required leaf‑to‑root string. Store each generated string in a list and compare them lexicographically after traversal to find the smallest one. This approach is straightforward because it separates traversal and comparison logic. The drawback is memory usage: storing every leaf string can take O(n * h) space in skewed trees where many paths are long.

Approach 2: DFS with Backtracking and Running Minimum (Time: O(n * h), Space: O(h))

A more efficient solution performs a single DFS while maintaining the current path using a mutable structure such as a list or string builder. Each node contributes a character computed with chr(ord('a') + node.val). When the traversal reaches a leaf, construct the candidate string by reversing the path and compare it directly with the current best result. If the candidate is lexicographically smaller, update the answer. Backtracking removes the last character before returning to the parent node, keeping the path accurate for sibling branches.

This method avoids storing all candidate strings. Only the current traversal path of length h is kept in memory, where h is the tree height. The algorithm still visits every node once in the binary tree, but comparisons happen only when reaching leaves. Because string comparisons may examine up to h characters, the total time complexity becomes O(n * h). The approach naturally fits recursive DFS patterns commonly used for tree problems.

Recommended for interviews: The DFS with backtracking approach is the expected solution. Interviewers want to see that you can traverse a tree while maintaining a path and update results only at leaf nodes. Mentioning the simpler "store all strings" version shows understanding of the problem, but implementing the in‑place DFS solution demonstrates stronger control of recursion, path tracking, and lexicographic comparison.

Approach 1: Depth-First Search (DFS)

In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.

This solution uses a DFS approach to explore all paths from leaf nodes to the root. We build the path string by prepending the current node's character (converted from the node's value) to the path. Upon reaching a leaf node, we compare the constructed path to the smallest recorded path. If it's smaller, we update our smallest value. Finally, we use recursion to explore both left and right children of each node.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS)

Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS storing all leaf stringsO(n * h)O(n * h)Useful for quick implementation or debugging when memory is not a concern
DFS with backtracking and running minimumO(n * h)O(h)Preferred interview solution; minimizes memory and processes each path during traversal

Video Solution

Smallest String Starting From Leaf - Leetcode 988 - Python • NeetCodeIO • 12,006 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest String Starting From Leaf easy or hard?
Smallest String Starting From Leaf is generally considered a Medium difficulty problem. The traversal itself is straightforward DFS, but handling path construction, reversing strings correctly, and performing lexicographic comparisons during recursion adds moderate complexity.
Smallest String Starting From Leaf Python/Java solution
In Python or Java, implement a recursive DFS function that tracks the current path. Convert node values to characters using 'a' + value, append to the path, and when a leaf is reached compare the reversed string with the current best result. After exploring children, remove the last character to backtrack.
How to solve Smallest String Starting From Leaf in O(n)?
Traversal of the tree itself is O(n) using Depth-First Search, since every node is visited once. The overall complexity becomes O(n * h) because candidate strings may require comparisons up to the height of the tree. Implement DFS with backtracking, maintain the path characters, and update the smallest lexicographic string whenever a leaf is reached.
What is the best approach for Smallest String Starting From Leaf?
Depth-First Search (DFS) with backtracking is the best approach. Traverse the tree while maintaining the current path of characters. When a leaf node is reached, reverse the path to form the leaf‑to‑root string and compare it with the smallest string found so far. This method processes the tree in one pass and keeps only the current path in memory.
Is Smallest String Starting From Leaf asked at Google/Amazon/Meta?
Tree traversal and DFS path problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that involve building strings from tree paths or comparing lexicographic results are common because they test recursion, backtracking, and binary tree traversal skills.
What data structure is used in Smallest String Starting From Leaf?
The main data structure is a binary tree combined with a DFS traversal stack (implicit through recursion). A list or string builder is used to maintain the current path of characters during traversal. Backtracking removes characters as recursion returns to parent nodes.
What is the time complexity of Smallest String Starting From Leaf?
The time complexity is O(n * h), where n is the number of nodes and h is the height of the tree. Each node is visited once during DFS, and when a leaf is encountered the algorithm may compare strings up to length h. Space complexity is O(h) due to the recursion stack and current path storage.

Ready to solve this problem?

Practice Smallest String Starting From Leaf with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Paths

Next

Sum Root to Leaf Numbers