Google Interview Question Software Engineer in Tests
0of 0 votesFind the least common ancestor .
I guess I have a solution...why don't we store the paths from root to node A in one array and path from root to node B in another array...(as its a tree , there will be only one path..)...and then from the beginning scan both the arrays till we get an index for which the values are different..The value at the previous index will give me the least common ancestor....
Please find any errors in this approach..
This is a classic problem.
The ambiguous parts here are:
1. Is the input tree a binary tree?
2. If it is a binary tree, is it a BST?
3. Do we have a pointer from each node to parent?
I would assume the given input is a valid tree; that is, there are no circles (which makes it a directed graph).
Let's say the easiest case. Binary Tree.
Input two node, a and b. We start travel from the root, wishing to find a node x such that x is between a and b.
/* Assme root != null, node1 != null, node2 != null */
public BTree lca(BTree root, BTree node1, BTree node2) {
while (root != null) {
if (root.value >= node1.value && root.value >= node2.value)
root = root.left;
else if (root.value < node1.value && root.value < node2.value)
root = root.right;
else
return root;
}
return root;
}
Assume it is a binary tree, but not BST.
If we have pointers to parent. The problem can still be solved in O(logn).
View the path from a node to the parent as a linked list. The problem is translated into finding the interestion of two linked list.
First find the depth of each node. Say one node has depth x, and the other node has depth y. Assume x > y. Then we move up the first node by (x - y). Thereafter, the distance between LCA and each of the two node are the same.
public int findDepth(BTree tree) {
int depth = 0;
while ((tree = tree.parent) != null)
depth++;
return depth;
}
public BTree moveUp(BTree tree, int level) {
while (tree != null && level-- > 0)
tree = tree.parent;
return tree;
}
public BTree lca(BTree node1, BTree node2) {
int depth1 = findDepth(node1);
int depth2 = findDepth(node2);
int diff = depth1 - depth2;
if (diff > 0) {
node1 = moveUp(node1, diff);
} else {
node2 = moveUp(node2, -diff);
}
while (node1 != node2 && node1 != null && node2 != null) {
node1 = node1.parent;
node2 = node2.parent;
}
return node1;
}
If there is no pointer to parent, and it's not BST, then we can use the naive approach to solve the problem in O(n^2).
Starting from root, test each children, and ask whether node1 and node2 are both offsprings of the node. Repeat this until we find a node such that it is a common ancestor of node1 and node2, but neither of its children is a common ancestor of the two nodes.
Test offspring/ancestor relationship would take O(n). And the until algorithm takes O(n^2).
IF BST
-----
Do Binary search(inorder) for both values and see how long you can travel in same direction, the node where you have go in different direction is the result. O(log n)
NOT BST
-------
Do a DFS and store that path for N1 and N2, The node where both path differs is the result. O(2N) = O(N).
boolean findAncestor(Node node, int value1, int value2) {
boolean found = false;
if(node != null) {
if(node.value == value1 || node.value == value2) {
found = true;
}
else {
boolean foundLeft = findAncestor(node.leftChild, value1, value2);
boolean foundRight = findAncestor(node.rightChild, value1, value2);
if(foundLeft && foundRight) {
System.out.println("ancestor = " + node);
}
found = foundLeft | foundRight;
}
}
return found;
}
A C# code:
- Anonymous July 20, 2010static int LeastCommonAncestor(BTNode node, int val1, int val2, ref BTNode lca) { int ret_l, ret_r, ret; if (node == null) return 0; ret_l = LeastCommonAncestor(node.left, val1, val2, ref lca); if (ret_l == 3) return 3; ret_r = LeastCommonAncestor(node.right, val1, val2, ref lca); if (ret_r == 3) return 3; if (node.val == val1) ret = 1; else if (node.val == val2) ret = 2; else ret = 0; ret |= ret_l | ret_r; if (ret == 3) { if (lca == null) lca = node; } return ret; }