988. Smallest String Starting From Leaf
Smallest String Starting From Leaf (LeetCode 988) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
How to solve Smallest String Starting From Leaf
Smallest String Starting From Leaf is a Preorder Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master preorder traversal for tree construction, inversion, and path problems. Visit root before children.
Work towards the solution in these steps:
- Consider using a depth-first search (DFS) traversal to explore all paths from root to leaves.
- Since the string must start from a leaf and end at the root, think about how to build the string in reverse order during traversal.
- At each leaf node, you can form a candidate string; keep track of the lexicographically smallest string found so far.
The reference solution runs in O(n + l * h) time and O(h) space.
The Smallest String Starting From Leaf solution and editorial walks through the full approach with reference code.
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
Topics and companies
Topics: String, Backtracking, Tree, Depth-First Search, Binary Tree.
Reported in interviews at Google.
How to practise Smallest String Starting From Leaf on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + l * h) time and O(h) space.
Open Smallest String Starting From Leaf in the code editor, or read the Smallest String Starting From Leaf editorial for a worked solution with its approach and complexity analysis.
Where Smallest String Starting From Leaf sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Preorder Traversal subpattern
- The full DSA patterns sheet
Problems related to Smallest String Starting From Leaf
Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Paths — Easy, same subpattern
- Binary Tree Preorder Traversal — Easy, same subpattern
- Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
- Construct Quad Tree — Medium, same subpattern
- Count Good Nodes in Binary Tree — Medium, same subpattern
- Flatten Binary Tree to Linked List — Medium, same subpattern
Smallest String Starting From Leaf FAQ
What is the LeetCode number of Smallest String Starting From Leaf?
Smallest String Starting From Leaf is LeetCode problem 988, rated Medium.
What pattern is used to solve Smallest String Starting From Leaf?
Smallest String Starting From Leaf is a Preorder Traversal problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
What is the time complexity of Smallest String Starting From Leaf?
The reference solution runs in O(n + l * h) time and O(h) space.
Which companies ask Smallest String Starting From Leaf?
Smallest String Starting From Leaf has been reported in interviews at Google.