Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.
int delta= depth(p) - depth(q); // get difference in depths
TreeNode first = delta > 0 ? q : p; // get shallower node
TreeNode second= delta > 0 ? p : q; // get deeper node
second= goUpBy(second, Math.abs(delta)); // move deeper node up
/* Find where paths intersect. */
while (first != second && first != null && second != null) {
first= first.parent;
second= second.parent;
}
return first== null || second == null ? null : first;
}
TreeNode goUpBy(TreeNode node, int delta) {
while (delta> 0 && node != null) {
node= node.parent;
delta--;
}
return node;
}
int depth(TreeNode node) {
int depth= 0;
while (node != null) {
node = node.parent;
depth++;
}
return depth;
}
This problem is equivalent to finding the first common node in two intersected lists.
The best solution:A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is alwaysdh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?
The best solution:A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is alwaysdh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?
The reason is simple, if we advance the deeper node dh steps above, both nodes would be at the same depth. Then, we advance both nodes one level at a time. They would then eventually intersect at one node, which is the LCA of both nodes.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
int getHeight(Node *p) {
int height = 0;
while (p) {
height++;
p = p->parent;
}
return height;
}
// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
int h1 = getHeight(p);
int h2 = getHeight(q);
// swap both nodes in case p is deeper than q.
if (h1 > h2) {
swap(h1, h2);
swap(p, q);
}
// invariant: h1 <= h2.
int dh = h2 - h1;
for (int h = 0; h < dh; h++)
q = q->parent;
while (p && q) {
if (p == q) return p;
p = p->parent;
q = q->parent;
}
return NULL; // p and q are not in the same tree
}
An easy solution:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.
The run time complexity of this approach is O(h), where h is the tree’s height. The space complexity is also O(h), since it can mark at most 2h nodes
A variation of this problem which seemed to be more popular is:
Given two singly linked lists and they both intersect at one point (ie, forming a Y shaped list). Find where the two linked lists merge. |
public static void swap(TreeNode a, TreeNode b) { final TreeNode temp = a; a = b; b = temp; } public static void swap(int a, int b) { final int temp = a; a = b; b = temp; } public static int getHeight(TreeNode p) { int height = 0; while (p != null) { height++; p = p.parent; } return height; } // As root->parent is NULL, we don't need to pass root in. TreeNode LCA(TreeNode p, TreeNode q) { final int h1 = getHeight(p); final int h2 = getHeight(q); // swap both nodes in case p is deeper than q. if (h1 > h2) { swap(h1, h2); swap(p, q); } // invariant: h1 <= h2. final int dh = h2 - h1; for (int h = 0; h < dh; h++) { q = q.parent; } while (p != null && q != null) { if (p == q) { return p; } p = p.parent; q = q.parent; } return null; // p and q are not in the same tree }
Without parent pointer
One first idea is to start from the root and recursively traverse down until we hit ether of the nodes then-
One first idea is to start from the root and recursively traverse down until we hit ether of the nodes then-
- If we found both nodes in the left subtree then recurse the above procedure starting from the left child of root.
- Else if, we found both nodes in the right subtree then recurse the above procedure starting from the right child of root.
- Else if we found one on left and other on right then return root.
- else if we didn’t find one or both then return null.
This above algorithm is a top down approach and the search spaces are overlapping i.e. we are traversing some part of the tree many times. We can skip overlapping search space by traversing from bottom up as follows.
- While traversing from the bottom recursively if we reach a one of the given nodes, we pass it up to its parent.
- Then we will check from the parent whether either of the nodes is in left or right subtree.
- If it is then the parent must be the LCA. We pass its parent up to the root.
- If not then we pass up to the parent the root of the subtree (left or right) node which contains either one of the two nodes, or NULL if neither subtree contains the nodes .
public static BTNode LCA(BTNode root, BTNode x, BTNode y) { if (root == null) return null; if (root == x || root == y) return root; BTNode leftSubTree = LCA(root.left, x, y); BTNode rightSubTree = LCA(root.right, x, y); //x is in one subtree and and y is on other subtree of root if (leftSubTree != null && rightSubTree != null) return root; //either x or y is present in one of the subtrees of root or none present in either side of the root return leftSubTree!=null ? leftSubTree : rightSubTree; }
LCA of BST
public static TreeNode LowestCommonAnchestorBST(TreeNode root, final TreeNode p, final TreeNode q) { if (root == null) { return null; } while (root != null) { if (root.key > p.key && root.key > q.key) { root = root.left; } else if (root.key < p.key && root.key < q.key) { root = root.right; } else { return root; } } return null; }
This approach will take 0( d) time, where d is the depth of the deeper node.
TreeNode commonAncestor(TreeNode p, TreeNode q) {int delta= depth(p) - depth(q); // get difference in depths
TreeNode first = delta > 0 ? q : p; // get shallower node
TreeNode second= delta > 0 ? p : q; // get deeper node
second= goUpBy(second, Math.abs(delta)); // move deeper node up
/* Find where paths intersect. */
while (first != second && first != null && second != null) {
first= first.parent;
second= second.parent;
}
return first== null || second == null ? null : first;
}
TreeNode goUpBy(TreeNode node, int delta) {
while (delta> 0 && node != null) {
node= node.parent;
delta--;
}
return node;
}
int depth(TreeNode node) {
int depth= 0;
while (node != null) {
node = node.parent;
depth++;
}
return depth;
}
Solution #2: With Links to Parents (Better Worst-Case Runtime)
This algorithm takes O(t) time, where tis the size of the subtree for the first common ancestor. In the
worst case, this will be O( n), where n is the number of nodes in the tree. We can derive this runtime by
noticing that each node in that subtree is searched once.
TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/* Check if either node is not in the tree, or if one covers the other. */
if (!covers(root, p) || !covers(root, q)) {
return null;
}else if (covers(p, q)) {
return p;
} else if (covers(q, p)) {
return q;
}
/* Traverse upwards until you find a node that covers q. */
TreeNode sibling= getSibling(p);
TreeNode parent= p.parent;
while (!covers(sibling, q)) {
sibling= getSibling(parent);
parent= parent.parent;
}
return parent;
}
boolean covers(TreeNode root, TreeNode p) {
if (root== null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
TreeNode getSibling(TreeNode node) {
if (node== null || node.parent == null) {
return null;
}
TreeNode parent = node.parent;
return parent.left== node ? parent.right : parent.left;
}
Read full article from Lowest Common Ancestor of a Binary Tree Part II | LeetCode
