Amazon Interview Question: Binary tree with parent point... | Glassdoor

Interview Question

Software Design Engineer Interview Seattle, WA

Binary tree with parent pointers, given two nodes find

  common ancestor.
data structures, programming

Interview Answer

3 Answers


Hint: use a hash table

Interview Candidate on Mar 19, 2009

For each node traversed from the root,
if both values are less than the current Node, then move to the left
if both values are greater than the currentNode, then move to the right,
if the value of current Node is between value 1 and value 2, then you have found the nearest common ancestor.

Rajiv on Aug 23, 2010

Rajiv, you can't do that is tree is by parent pointers. you need to bubble up from the given nodes and put parents to a hash.

dantepy on Apr 30, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.