Sponsored
Sponsored
In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.
Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
1var smallestFromLeaf = function(root) {
2 let smallest = "~";
3 const dfs = (node, path) => {
4 if (!node) return;
5 path = String.fromCharCode(node.val + 97) + path;
6 if (!node.left && !node.right) {
7 if (path < smallest) smallest = path;
8 }
9 dfs(node.left, path);
10 dfs(node.right, path);
11 };
12 dfs(root, "");
13 return smallest;
14};The JavaScript solution utilizes a recursive DFS function to traverse the tree, updating a path string with each node it visits. Upon encountering a leaf node, if its path proves to be lexicographically smaller than previously recorded paths, the `smallest` variable is altered to reflect this fact.