Google Phone Interview Question - Android Team - Mountain View, CA
Anonymous User
581
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.
Comments (5)