Question
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
_______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4
If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.
Hint:
Top-down or bottom-up? Consider both approaches and see which one is more efficient.
This question appears on CC150v5 Q4.7.
Analysis
This tree is not BST, so it’s more difficult then previous. Top-down approach would take O(n2) time due to duplicate traverse.
However, there is a very good bottom-up approach with O(n) time. This solution, though very tricky, is the most standard and common interview question that can be asked about Binary Tree.
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.
The coding is very concise.
Notes:
The LCA problem had been studied extensively by many computer scientists. There exists efficient algorithms for finding LCA in constant time after initial processing of the tree in linear time. For the adventurous reader, please read this article for more details: Range Minimum Query and Lowest Common Ancestor in Topcoder.
Code
updated on Sep 15th, 2014: code from CC150v5 Q4.7
public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
} else if (root == p) {
return p;
} else if (root == q) {
return q;
}
if (commonAncestor(root.left, p, q) == null) {
return commonAncestor(root.right, p, q);
} else if (commonAncestor(root.right, p, q) == null) {
return commonAncestor(root.left, p, q);
} else {
return root;
}
}