Pretty standard problem asked https://leetcode.com/problems/closest-leaf-in-a-binary-tree/description/. Instead of the closest leaf we needed to return the value.
I discussed approach:
construct path from root to node
reverse iterate path & for each node
> check whole subtree for matching node
> otherwise, check closest leaf in alternate direction compared to child direction for each parent node
Now my suffering starts with follow ups:
why do you need to store path? Why can't you do it while traversing? I said we can do while traversing but we need to return the closest leaf node & distance which may convulate the function so trying to separate. Interviewer said okay lets do that as a follow up.
I then tried writing the getClosestLeafDist function & interviewer started pinpointing with line numbers continuosly, why doing DFS do BFS. This line has NPE, blah-blah blah-blah. He threw me off my whole flow & trust me I have solved this problem on leetcode multiple times before.
He then tells me that this can be done in 10 lines, why are you doing this with 3 functions?
I mean he genuinely grills me for the entire 1 hour. On the middle of the interview he keeps pasting test cases on codepad & creates continuous compilation errors, does not let me finish my reasoning. I keep telling him if tree is skewed dfs will anyways cause O(h) space complexity ~ god knows what these guys expect. If you cannot give the interviewee their space to be themselves & perform how would they be able to code 2 medium=hard's in 1 hour?
I tried writing below code in the interview
public class Linkedin {
List<TreeNode> path;
public int FindClosestLeaf(TreeNode root, int k) {
GetPath(root, k, new List<TreeNode>());
int minLeafDistance = 1001;
minLeafDistance = Math.Min(minLeafDistance, getClosestLeafDist(path.Last()));
for(int i=path.Count-2; i >= 0; i--){
TreeNode current = path[i];
TreeNode next = path[i+1];
int dist = 1001;
if(next == current.left && current.right != null){
dist = getClosestLeafDist(current.right) + 1;
} else if(next == current.right && current.left != null){
dist = getClosestLeafDist(current.left) + 1;
}
minLeafDistance = Math.Min(minLeafDistance, dist + (path.Count-i-1));
}
return minLeafDistance;
}
private void GetPath(TreeNode root, int k, List<TreeNode> pth){
if(root == null){
return;
}
pth.Add(root);
if(root.val == k){
this.path = new List<TreeNode>(pth);
return;
}
GetPath(root.left,k,pth);
GetPath(root.right,k,pth);
pth.RemoveAt(pth.Count-1);
}
private int getClosestLeafDist(TreeNode root){
if(root == null || (root.left == null && root.right == null)){
return 0;
}
if(root.left == null){
return 1 + getClosestLeafDist(root.right);
}
if(root.right == null){
return 1 + getClosestLeafDist(root.left);
}
return Math.Min(getClosestLeafDist(root.left), getClosestLeafDist(root.right)) + 1;
}
}