Smallest String Starting From Leaf

Smallest String Starting From Leaf 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.

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), l is the number of leaves 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
• All coding practice problems

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
• Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
• Flatten Binary Tree to Linked List — Medium, same subpattern
• Invert Binary Tree — Easy, same subpattern
• Same Tree — Easy, same subpattern
• Symmetric Tree — Easy, same subpattern