Given a binary unsorted tree, determine the path from two given nodes i.e 5 and 8.
Note: 5, 8 are values and not node pointers.
Assumption: Nodes are unique
input: [ root(1), 5 , 8]
output: "up" -> "right" -> "left.
start node pointer(5) should always add "up" going upwards towards root of tree. if the destination node it should be traversed and added in "left" or "right" fashion.
1
5 4
9 10 8. 11
input: [ root(1), 5 , 8]
output: "up" -> "right" -> "left.
1
5
8
11
input: [ root(1), 5, 8]
output: "up" i.e from 8 ->5
It was a 45 min interview.
My approach: 1. Finding LCA first
2. swap if start is parent of destination node.
3. traverse and apply up and "left" or "right" rule.
Took me some time to get there but interviewer said this is good and can be optimized further.