Smallest Leaf-to-Root Word

Medium

You are given the root of a binary tree. Every node holds a number from 0 to 25 standing for a letter: 0 is a, 1 is b, ..., 25 is z. Pick any leaf (a node with no children) and read the letters while climbing from it up to the root; that spells a word. Return the lexicographically smallest of all such words. As a reminder, strings are compared by their first differing letter, and if one is a prefix of the other, the shorter one is smaller: "ab" comes before "aba".

Example 1

root=tree_node([2, 0, 1, None, None, 3, 0]) → 'abc'

There are three leaves, giving "ac", "dbc" and "abc". The smallest is "abc": its second letter "b" already beats "c".

Example 2

root=tree_node([0, 1]) → 'ba'

The only leaf is "b", and reading up to the root gives "ba".

Example 3

root=tree_node([25, 0, 0, 1]) → 'az'

The words are "baz" and "az"; "az" is smaller because the comparison looks at the first letter that differs.

Constraints

The tree has between 1 and 8500 nodes
0 ≤ Node.val ≤ 25

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search String Backtracking Binary Tree

Similar problems

Routes from Root to Leaves Easy All Leaf Paths With a Given Total Medium Tree From Bracket Notation Medium Tree in Compact Brackets Medium Directions Through a Tree Medium

Input

root=tree_node([2, 0, 1, None, None, 3, 0])

Expected

'abc'

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.