Lexicographically Smallest Leaf to Root Path- Google Top Interview Questions

                        Solution in C++ :

string Solve(Tree* root, string s = "") {
    if (root == nullptr) {
        return "|";
    }
    s = string(1, 'a' + root->val) + s;
    if (root->left == root->right) {
        return s;
    }

    return min(Solve(root->left, s), Solve(root->right, s));
}

vector<int> solve(Tree* root) {
    string result = Solve(root);
    vector<int> res;
    for (auto& ch : result) {
        res.emplace_back(int(ch - 'a'));
    }
    return res;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int[] solve(Tree root) {
        return traverse(root, new int[] {});
    }

    int[] smallest = null;
    public int[] traverse(Tree root, int[] path) {
        if (root == null)
            return smallest;

        int[] newPath = new int[path.length + 1];
        System.arraycopy(path, 0, newPath, 1, path.length);
        newPath[0] = root.val;

        if (root.left == null && root.right == null) {
            if (smallest == null || lexSmaller(newPath, smallest))
                smallest = newPath;
        }

        traverse(root.left, newPath);
        traverse(root.right, newPath);

        return smallest;
    }

    public boolean lexSmaller(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (i > b.length)
                return false;
            if (a[i] < b[i])
                return true;
            if (a[i] > b[i])
                return false;
        }
        return true;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        res = ""

        def dfs(root, path=""):
            nonlocal res
            path = str(root.val) + path
            if not root.left and not root.right:
                if res == "" or path < res:
                    res = path
                return

            if root.left:
                dfs(root.left, path)
            if root.right:
                dfs(root.right, path)

        if root:
            dfs(root)
        return [int(v) for v in res]