988. Smallest String Starting From Leaf

MediumTreeDepth-First SearchStringBinary Tree

Problem Description

In this problem, we are provided with the root of a binary tree where each node has a value within the range [0, 25]. These values represent the letters 'a' to 'z'. The task is to find the lexicographically smallest string that starts at a leaf of the tree and ends at the root. A leaf is defined as a node with no children. In terms of string comparison, a shorter prefix of a string is considered lexicographically smaller.

Intuition

The problem is essentially asking us to find the lexicographically smallest path from a leaf node to the root. Since the lexicographically smaller string could be due to a shorter length, we should aim to find shorter paths first.

We can solve this problem using a Depth-First Search (DFS) approach that will explore all paths from the root to the leaves and keep track of the lexicographically smallest path found at any point. Here's how we can proceed:

Traverse the tree starting from the root node and going down towards the leaves using DFS.
As we traverse, construct the string representing the path from the current leaf to the root by appending characters corresponding to node values at each step.
When a leaf node is reached, we reverse the constructed string (as we want it from leaf to root, but we are moving from root to leaf) and compare it with the currently found lexicographically smallest string. If it’s smaller, we update the smallest string.
After the DFS is completed, we will have the lexicographically smallest string from any leaf to the root.

A crucial detail is to handle the string comparison efficiently. Using Python's built-in string comparison, we can directly compare the strings using the min function. It's also important to note that we need to reverse the constructed path only once when we reach a leaf to avoid unnecessary computation.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

O(1)O(n)O(n!)O(n^n)

I don’t know

Solution Approach

The solution approach involves a Depth-First Search (DFS) algorithm that traverses the binary tree and efficiently constructs strings from leaves to root. During traversal, it keeps track of the smallest string found. Here's the detailed implementation described in steps:

Character Conversion: Since node values are integers in the range [0, 25], the first step is to convert the node values into characters. This is done by adding the node value to the ASCII value of 'a', which is done using chr(ord('a') + root.val).
DFS Function (dfs): A recursive function dfs is defined, which takes the root node and the current path as arguments. The path argument is a list that stores the characters from the root to the current node. This function is responsible for DFS traversal and updates the smallest string.
Base Case: The base case for the DFS is when the root is None. In this case, the function returns without performing any action.
Path Construction: When the root is not None, the corresponding character for the node value is appended to the path. If the root is a leaf (both root.left and root.right are None), the complete path from the root to this leaf is evaluated for lexicographical order.
Leaf String Reversal and Comparison: Upon reaching a leaf node, the path is reversed to make the string start at the leaf and end at the root, and the lexicographically smallest string ans is updated by comparing the current string with the existing smallest string using min(ans, ''.join(reversed(path))).
DFS Recursion: The function then recursively calls itself for the left and right children of the current node if they exist, enabling traversal of the entire tree.
Backtracking: After exploring both subtrees (left and right) from the current node, it's important to remove the current node's character from the path. This is to backtrack and ensure that when moving to a different branch, the path is correctly maintained - hence path.pop() is used.
Global Smallest String (ans): A variable ans is initialized to a string value higher than any possible value from the tree (the ASCII value of 'z' plus one), and it's defined as nonlocal within the dfs function to allow updating its value across recursive calls.

The specified approach takes advantage of the recursive nature of DFS to explore all paths from the root to leaf nodes and employs backtracking to efficiently update the paths during traversal. Additionally, Python's concise syntax and string comparison capabilities are leveraged to keep the implementation clean and readable.

Algorithm Complexity: The time complexity is O(N * M), where N represents the number of nodes in the tree and M is the maximum depth of the tree, since we need to compare strings of length M for each leaf node. The space complexity is O(M), which is required for the recursion stack and the path list in the worst case when the tree is skewed.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayMerge sort does not use divide and conquer

I don’t know

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider a binary tree structured like this, where each node's value represents a character ('a' to 'z'):

1   b
2  / \
3 a   d
4    / \
5   c   e

This tree can be represented as the following with numerical values [0, 25] (where 'a' = 0, 'b' = 1, ..., 'z' = 25):

We want to find the lexicographically smallest string from a leaf to the root.

Step 1: Initializing the smallest string ans as "{" (ASCII value just above 'z') to ensure any valid path is smaller than ans initially.

Step 2: We start DFS from the root node 'b' ('b' has a numerical value of 1).

Step 3: The dfs function is called with the root node 'b'. We add 'b' to the current path.

Step 4: The root node has two children. The dfs function is recursively called on the left child 'a'.

Step 5: Now at node 'a'. It is a leaf node, so we reverse the current path which gives us "ab". We compare it with ans and update ans to "ab" as it is lexicographically smaller.

Step 6: Backtracking occurs, and we remove 'a' from the path and return to the root node 'b'.

Step 7: Next, the dfs is recursively called on the right child 'd'.

Step 8: At node 'd', we continue the process by moving to its left child 'c', which is also a leaf. The path here is "bdc". Reversed, we get "cdb". This string is not smaller than "ab", so ans remains "ab".

Step 9: We backtrack again and go to the right child 'e', encountering the path "bde". When reversed, we get "edb". Again, this is not smaller than "ab".

Step 10: DFS completes after we have visited all leaf nodes. ans is "ab", which is the lexicographically smallest string from leaf to root.

Thus, the lexicographically smallest string from a leaf to the root is "ab".

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def smallestFromLeaf(self, root: TreeNode) -> str:
10        # Initialize the answer variable with a dummy string value that is higher than any other valid strings
11        smallest_string = '{'  # '{' is the character immediately after 'z' in ASCII
12
13        def dfs(node, path):
14            nonlocal smallest_string
15            if node:
16                # Convert current node's value to corresponding lowercase letter and prepend to path
17                path.append(chr(ord('a') + node.val))
18              
19                # Check if current node is a leaf node (no children)
20                if node.left is None and node.right is None:
21                    # Create string from leaf to root and update smallest_string if necessary
22                    current_string = ''.join(reversed(path))
23                    smallest_string = min(smallest_string, current_string)
24              
25                # Continue depth-first search in left and right subtrees
26                dfs(node.left, path)
27                dfs(node.right, path)
28
29                # Backtrack: remove the current node's character from path
30                path.pop()
31
32        # Start depth-first search from the root node
33        dfs(root, [])
34        return smallest_string
35

1/**
2 * Definition for a binary tree node.
3 */
4public class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode() {}
10
11    TreeNode(int val) {
12        this.val = val;
13    }
14
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    private StringBuilder currentPath; // StringBuilder to store the current path from leaf to root.
24    private String smallestPath; // String to keep track of the smallest path encountered.
25
26    public String smallestFromLeaf(TreeNode root) {
27        currentPath = new StringBuilder();
28        // Initialize the smallest path with a string value greater than any possible leaf path.
29        smallestPath = String.valueOf((char) ('z' + 1));
30        // Start the depth-first search from the root.
31        depthFirstSearch(root);
32        // Return the smallest path from leaf to root.
33        return smallestPath;
34    }
35
36    private void depthFirstSearch(TreeNode node) {
37        if (node != null) {
38            // Prepend the character representation of the current node's value to the path.
39            currentPath.append((char) ('a' + node.val));
40          
41            // Check if it's a leaf node.
42            if (node.left == null && node.right == null) {
43                // Reverse the path to get the leaf to root string.
44                String leafToRootPath = currentPath.reverse().toString();
45              
46                // Update the smallest path if the current path is smaller.
47                if (leafToRootPath.compareTo(smallestPath) < 0) {
48                    smallestPath = leafToRootPath;
49                }
50              
51                // Reverse the path back to maintain the root to leaf order.
52                currentPath.reverse();
53            }
54          
55            // Continue the depth-first search to the left subtree.
56            depthFirstSearch(node.left);
57            // Continue the depth-first search to the right subtree.
58            depthFirstSearch(node.right);
59          
60            // Backtrack: remove the last character representing the current node's value.
61            currentPath.deleteCharAt(currentPath.length() - 1);
62        }
63    }
64}
65

1#include <algorithm> // Include for the reverse function
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    string smallestLeafString = ""; // Holds the lexicographically smallest string from leaf to root.
16
17    // Entry point to find the smallest string from leaf to root.
18    string smallestFromLeaf(TreeNode* root) {
19        string path = "";         // Represents the current path as a string.
20        dfs(root, path);          // Start the DFS traversal.
21        return smallestLeafString; // Return the smallest string after traversing the whole tree.
22    }
23
24    // Depth First Search (DFS) to traverse the tree.
25    void dfs(TreeNode* node, string& path) {
26        if (!node) return; // Base case: if the current node is nullptr, end the recursion.
27
28        // Append the current character represented by the node's value to the path.
29        path += 'a' + node->val;
30
31        if (!node->left && !node->right) { // Check if it's a leaf node.
32            string pathReversed = path;    // Create a copy of the current path to reverse it.
33            reverse(pathReversed.begin(), pathReversed.end()); // Reverse the string to get the path from leaf to root.
34            // Set smallestLeafString to the pathReversed if it's smaller than the current smallestLeafString or if smallestLeafString is empty.
35            if (smallestLeafString.empty() || pathReversed < smallestLeafString) {
36                smallestLeafString = pathReversed;
37            }
38        }
39
40        // Continue the DFS traversal for both children.
41        dfs(node->left, path);
42        dfs(node->right, path);
43
44        // Backtrack: Remove the last character as we return to the previous node.
45        path.pop_back();
46    }
47};
48

1// Import necessary functionality for reversing strings.
2import { reverse } from "algorithm";
3
4// Definition for a binary tree node.
5class TreeNode {
6    val: number;
7    left: TreeNode | null;
8    right: TreeNode | null;
9
10    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17// Holds the lexicographically smallest string from leaf to root.
18let smallestLeafString: string = "";
19
20// Entry point to find the smallest string from leaf to root.
21function smallestFromLeaf(root: TreeNode | null): string {
22    // Represents the current path as a string.
23    let path: string = "";
24    // Start the DFS traversal.
25    dfs(root, path);
26    // Return the smallest string after traversing the whole tree.
27    return smallestLeafString;
28}
29
30// Depth First Search (DFS) to traverse the tree.
31function dfs(node: TreeNode | null, path: string): void {
32    // Base case: if the current node is null, end the recursion.
33    if (!node) return;
34
35    // Append the current character represented by the node's value to the path.
36    path += String.fromCharCode('a'.charCodeAt(0) + node.val);
37
38    // Check if it's a leaf node.
39    if (!node.left && !node.right) {
40        // Create a copy of the current path.
41        let pathReversed = path;
42        // Reverse the string to get the path from leaf to root.
43        pathReversed = reverse(pathReversed);
44        // Set smallestLeafString to the pathReversed if it's smaller than the current smallestLeafString or if smallestLeafString is empty.
45        if (!smallestLeafString || pathReversed < smallestLeafString) {
46            smallestLeafString = pathReversed;
47        }
48    }
49
50    // Continue the DFS traversal for both children.
51    if (node.left) dfs(node.left, path);
52    if (node.right) dfs(node.right, path);
53
54    // Backtrack: Remove the last character as we return to the previous node.
55    path = path.substr(0, path.length - 1);
56}
57

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the number of nodes in the tree. This is because the depth-first search (DFS) algorithm implemented by the dfs function visits each node exactly once. During each visit, operations are performed that take constant time, such as appending to and popping from the path list, and making a comparison to update the ans variable when a leaf is encountered.

Space Complexity

The space complexity of the code can be considered as O(h), where h is the height of the tree. This space is used by the recursion stack during the depth-first traversal. In the worst case (e.g., a skewed tree), the height of the tree could be n, leading to a space complexity of O(n).

There's an additional space complexity involved with storing the path and the construction of the string for comparison, which becomes O(h) for the path list itself as it stores the characters representing the path from the root to the current node. The reversed(path) operation creates a temporary list to hold the reversed path, which takes O(h) space as well. However, since these are temporary and do not grow with n, the dominant factor remains the recursion stack, so the additional space is not typically accounted for in the overall space complexity calculation.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

988. Smallest String Starting From Leaf

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings