Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Smallest String Starting From Leaf (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a binary tree where each node contains a value between 0 and 25. These values correspond to the letters 'a' to 'z' (0 = 'a', 1 = 'b', ..., 25 = 'z').

Return the lexicographically smallest string that can be formed by starting from a leaf node (a node with no children) and ending at the root of the tree. The string formed should be the lexicographically smallest among all possible strings.

Remember, any shorter prefix of a string is lexicographically smaller. For example, in lexicographical order, "ab" is smaller than "aba".

Examples

Example 1:

  • Input: root = [0, 1, 2, null, 3, 3, 4]
Image
  • Expected Output: "dba"
  • Explanation: The strings formed from the leaf nodes to the root are "dba", "dca", and "eca". The smallest string is "dba".

Example 2:

  • Input: root = [4, 0, 1, 1, 3, 2, 3]
Image
  • Expected Output: "bae"
  • Explanation: The strings formed are "bae", "dae", "cbe", and "dbe". The smallest string is "bae".

Example 3:

  • Input: root = [1, 3, 2, 3, 4, 4, 3]
Image
  • Expected Output: "dcb"
  • Explanation: The strings formed are "ddb", "edb", "ecb", and "dcb". The smallest string is "dcb".

Constraints:

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

Try it yourself

Try solving this question

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible