Smallest String Starting From Leaf - Practice Coding Problems

Smallest String Starting From Leaf - Problem

Imagine you're working with a special binary tree where each node contains a letter from 'a' to 'z' (represented by values 0-25). Your task is to find the lexicographically smallest string that starts from any leaf node and travels up to the root.

Think of it like finding the "earliest" path in a dictionary - just like how "ab" comes before "aba" alphabetically. You need to explore all possible paths from leaves to root and return the one that would appear first in a dictionary.

Key Points:

A leaf node has no children
The string is built from leaf → root direction
Each node value (0-25) maps to letters 'a'-'z'
Return the lexicographically smallest such string

Example: If a path gives you nodes [7, 4, 11, 11, 14] from leaf to root, this translates to string "hello".

Input & Output

example_1.py — Basic Tree

$ Input: root = [0,1,2,3,4,3,4] Tree structure: a(0) / \ b(1) c(2) / | | \ d(3) e(4) d(3) e(4)

› Output: "dba"

💡 Note: There are four possible paths from leaves to root: "dba", "eba", "dca", "eca". The lexicographically smallest is "dba".

example_2.py — Single Path

$ Input: root = [25,1,3,1,3,0,2] Tree structure: z(25) / \ b(1) d(3) / | | \ b(1) d(3) a(0) c(2)

› Output: "adz"

💡 Note: The paths are "bbz", "ddz", "adz", "cdz". The smallest lexicographically is "adz".

example_3.py — Edge Case - Single Node

$ Input: root = [0] Tree structure: a(0)

› Output: "a"

💡 Note: Single node tree, so the only path from leaf to root is just "a".

Constraints

The number of nodes in the tree is in the range [1, 8500]
0 ≤ Node.val ≤ 25
Each node value represents a letter from 'a' to 'z' (0 = 'a', 1 = 'b', ..., 25 = 'z')
Important: The string is built from leaf to root, not root to leaf

Visualization

Tap to expand

Understanding the Visualization

Start DFS

Begin traversal from root with empty string

Build Upward

At each node, prepend its letter to current path string

Check Leaves

When reaching a leaf, compare current string with minimum found

Track Minimum

Keep the lexicographically smallest string throughout traversal

Return Result

After visiting all paths, return the globally smallest string

Key Takeaway

🎯 Key Insight: Build strings during DFS traversal and compare immediately at leaves, avoiding the need to store all paths. This optimizes both time and space complexity while maintaining correctness.

Asked in

G Google 42 a Amazon 38 ⊞ Microsoft 25 f Meta 18

The optimal approach uses DFS traversal to build strings from leaf to root during traversal, comparing them on-the-fly without storing all paths. This achieves O(n) time and O(h) space complexity, where h is the tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS (Single Pass)	O(n)	O(h)	Build and compare strings during DFS traversal without storing all paths
Brute Force (Collect All Paths)	O(n²)	O(n*h)	Find all leaf-to-root paths, convert to strings, then find minimum

Optimized DFS (Single Pass) — Algorithm Steps

Start DFS from root with empty string
At each node, prepend character to current string
When reaching a leaf, compare current string with global minimum
Update global minimum if current string is smaller
Backtrack and continue with other paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin at root with empty string

Build String

Prepend character at each node

Check Leaf

Compare string when reaching leaf

Update Minimum

Keep track of lexicographically smallest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

char globalMin[1000];

void dfs(struct TreeNode* node, char* path, int len) {
    if (!node) return;
    
    // Prepend current character (shift existing and add at beginning)
    for (int i = len; i >= 0; i--) {
        path[i + 1] = path[i];
    }
    path[0] = 'a' + node->val;
    path[len + 1] = '\0';
    
    // If leaf node, update global minimum
    if (!node->left && !node->right) {
        if (strlen(globalMin) == 0 || strcmp(path, globalMin) < 0) {
            strcpy(globalMin, path);
        }
        return;
    }
    
    // Continue DFS
    dfs(node->left, path, len + 1);
    dfs(node->right, path, len + 1);
}

char* smallestFromLeaf(struct TreeNode* root) {
    char path[1000];
    globalMin[0] = '\0';
    path[0] = '\0';
    dfs(root, path, 0);
    return globalMin;
}

int main() {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 0; // 'a'
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    
    root->left->val = 1; // 'b'
    root->right->val = 2; // 'c'
    
    root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    
    root->left->left->val = 3; // 'd'
    root->left->right->val = 4; // 'e'
    root->right->left->val = 3; // 'd'
    root->right->right->val = 4; // 'e'
    
    // Set all leaf children to NULL
    root->left->left->left = root->left->left->right = NULL;
    root->left->right->left = root->left->right->right = NULL;
    root->right->left->left = root->right->left->right = NULL;
    root->right->right->left = root->right->right->right = NULL;
    
    char* result = smallestFromLeaf(root);
    printf("Smallest string: %s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once, string operations are O(h) where h is height

✓ Linear Growth

Space Complexity

O(h)

Recursion depth and current path string, where h is tree height

✓ Linear Space

42.8K Views

Medium Frequency

~18 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS (Single Pass) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler