Smallest String Starting From Leaf

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Every node of the given binary tree holds a value from 0 to 25, standing for the letters 'a' to 'z'. For each leaf, read the letters on the path from that leaf **up to the root** to form a string. Return the lexicographically smallest of these strings. Lexicographic order is the usual dictionary order; a string that is a proper prefix of another is the smaller one (for example "ab" < "aba").

Examples

Input: root = [0,1,2,3,4,3,4]
Output: "dba"
The leaf-to-root strings are dba, eba, dca and eca.
Input: root = [25,1,3,1,3,0,2]
Output: "adz"
Candidates are bbz, dbz, adz and cdz.
Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"
Candidates are abcc and abc. abc is a proper prefix of abcc, so it is smaller.

Constraints

  • 1 <= number of nodes <= 8500
  • 0 <= Node.val <= 25

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems