You're given a binary tree and pointers to two nodes in the tree. Describe the fastest algorithm you can come up with to determine the closest common ancestor.

Question

You're given a binary tree and pointers to two nodes in the tree.  Describe the fastest algorithm you can come up with to determine the closest common ancestor.

Shards · Accepted Answer

If there is parent pointer, the answer is straightforward. The simplest of which is just to traverse up from 1 node and record all the nodes, then traverse up from the other node and find the first node that match the recorded nodes. This is O(lg n) in a balanced tree, O(n) in worst-case.

If there is no parent pointer, I'd use tree traversal (pre-, in-, or post- doesn't matter much). The closest common ancestor would be the only node that find one node on its left children (or itself) and the other node on its right children (or itself). This is O(n).

Sigiloso · Answer

This one is covered a lot on the web and in technical books, but every one I've seen assumes it's a binary search tree.  Here he didn't want me to assume it was a binary search tree.

blakdogg · Answer

I think I would go with a modified dfs which terminates early. I would need a global variable to indicate the closest ancestor;

//return 0 - none found, 1 - a found, 2 - b found, 3 - both found
public int modifiedDFS(Node node, Node a, Node b, int ) {
	int res=0;
    if (node) {
		if ((node.left == a) || (node.right == a)) {
			res += 1;
		}
	
		if ((node.left == b) || (node.right == b)) {
			res += 2;
		}
		
		if (res == 3) {
			lowest = node;
		} else {
			int l = modifiedDFS(node.right, a, b);
			int r = modifiedDFS(node.left, a, b);
			
			if ((l==3) || (r==3)) {
				//lower node is the one
				res = 3;
			} else {
				if ((3 == (l+r)) ||
					(3 == (l+res)) ||
					(3 == (r+res)) {
					//i am the lowest
					lowest = node;
					res = 3;
				} else {
					if ((l==1)||(r==1))
						res = 1;
					if ((2==l)||(2==r))
						res = 2;
				}
			}
		}
	}
	return res;
}

Sigiloso · Answer

That may or may not work (I didn't trace through the code), but there's a much simpler and faster way to do it.  Worst-case running time is O(lg n).  With yours, worst-case running time is O(n).

Remember: you're given a pointer to the nodes in question.  To traverse from a leaf node to the root is worst-case O(lg n) operations.  Think of something you could do to take advantage of that.

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas