# Lexicographically Smallest Leaf to Root Path- Google Top Interview Questions

### Problem Statement :

```Given a binary tree root containing digits from 0 to 9, return the lexicographically smallest leaf to root path.

Constraints

n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [1, [8, null, null], [7, [4, [6, null, null], [3, null, null]], [5, null, null]]]

Output

[3, 4, 7, 1]```

### Solution :

```                        ```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]```
```

## View More Similar Problems

Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing