Smallest String Starting From Leaf

Problem Statement

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.

Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

As a reminder, any shorter prefix of a string is lexicographically smaller.

• For example, "ab" is lexicographically smaller than "aba".

A leaf of a node is a node that has no children.

Example 1

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

Example 2

Input: root = [25,1,3,1,3,0,2]
Output: "adz"

Try here before watching the video.

Video Solution

Java Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    String smallestString = "";
    private void solve(TreeNode root, String currentString) {
        if(root == null) return;

        currentString = (char)(root.val + 'a') + currentString;
        if(root.left == null && root.right == null) {
            if(smallestString.isEmpty() || smallestString.compareTo(currentString) > 0) {
                smallestString = currentString;
            }
        }

        solve(root.left, currentString);

        solve(root.right, currentString);
    }

    public String smallestFromLeaf(TreeNode root) {
        solve(root, "");
        return smallestString;
    }
}

C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string smallestFromLeaf(TreeNode* root) {
        string smallestString;
        solve(root, "", smallestString);
        return smallestString;
    }

    void solve(TreeNode* root, string currentString, string& smallestString) {
        if (root == nullptr)
            return;

        currentString = static_cast<char>(root->val + 'a') + currentString;
        if (root->left == nullptr && root->right == nullptr) {
            if (smallestString.empty() || smallestString > currentString)
                smallestString = currentString;
        }

        solve(root->left, currentString, smallestString);
        solve(root->right, currentString, smallestString);
    }
};

Python Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        def solve(root, currentString):
            nonlocal smallestString
            if root is None:
                return

            currentString = chr(root.val + ord('a')) + currentString
            if root.left is None and root.right is None:
                if smallestString == "" or smallestString > currentString:
                    smallestString = currentString

            solve(root.left, currentString)
            solve(root.right, currentString)

        smallestString = ""
        solve(root, "")
        return smallestString

Javascript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var smallestFromLeaf = function(root) {
    let smallestString = '';
    
    const solve = (root, currentString) => {
        if (root === null) return;

        currentString = String.fromCharCode(root.val + 'a'.charCodeAt(0)) + currentString;
        if (root.left === null && root.right === null) {
            if (smallestString === '' || smallestString > currentString) {
                smallestString = currentString;
            }
        }

        solve(root.left, currentString);
        solve(root.right, currentString);
    };
    
    solve(root, '');
    return smallestString;
};

Go Code

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func smallestFromLeaf(root *TreeNode) string {
    var smallestString string
    solve(root, "", &smallestString)
    return smallestString
}

func solve(root *TreeNode, currentString string, smallestString *string) {
    if root == nil {
        return
    }

    currentString = string(rune(root.Val + 'a')) + currentString
    if root.Left == nil && root.Right == nil {
        if *smallestString == "" || *smallestString > currentString {
            *smallestString = currentString
        }
    }

    solve(root.Left, currentString, smallestString)
    solve(root.Right, currentString, smallestString)
}

Complexity Analysis

Time Complexity: O(N*N)
Space Complexity: O(N*N)