Node getLCA_BST(Node root, Node x, Node y):
Node curr = root
while !(x < curr && curr < y): // x.value < curr.value
if curr < x && curr < y:
curr = curr.right
else: //x < curr && y < curr
curr = curr.left
return curr // assume x and y are in the tree
[Hat tip to PIE]
In binary tree (BT), we have to:
- use a parent node pointer to get their paths in O(h) or O(logn) time
- find the intersecting node within the paths starting from root
Use a stack to save the paths for nodes x, y.
class TreeNode: int value TreeNode left TreeNode right TreeNode parent TreeNode getLCA_BT(TreeNode root, TreeNode x, TreeNode y): Stack sx = getPath(x) Stack sy = getPath(y) return getLCAFromPaths(sx, sy) Stack getPath(Node n): Stack sn = new Stack() while (n != null): sn.push(n) n = n.parent return sn TreeNode getLCAFromPaths(Stack sx, Stack sy): if sx == null || sy == null || sx.empty() || sy.empty(): throw lca = null while !sx.empty() && !sy.empty() && sx.peek() == sy.peek(): lca = sx.pop() sy.pop() //ignore return lca
[Hat tip to B.]
Without parent node:
If both nodes are present in current node's left subtree then recurse with left node. Same for right subtree and right node. The node where x, y are not in node's subtrees is the lca.
node lca-bt-check(node, x, y): if node == null: throw if x == null || y == null: throw lca = lca-bt(node, x, y) if lca == node && (!is-present(node, x) || !is-present(node, y)): throw return lca // inefficient node lca-bt(node, x, y): if node == null: return null if is-present(node.left, x) && is-present(node.left, y): return lca(node.left, x, y) if is-present(node.right, x) && is-present(node.right, y): return lca(node.right, x, y return node bool is-present(node, x): if node == null: return false if node == x: return true return is-present(node.left, x) || is-present(node.right, x)
Efficient way is to use the "bubble up" during dfs backtracking. Once x is found, bubble it up. Same for y. The very first node with a node's left and right as x and y (left and right are not null) is the lca. Once lca is found, bubble it up.
// efficient
node lca-bt(node, x, y):
if node == null:
return null
// node is x or y
if node == x || node == y:
return node
// bubble up lca
left = lca-bt(node.left, x, y)
if left != null && left != x && left != y:
return left
right = lca-bt(node.right, x, y)
if right != null && right != x && right != y:
return right
// lca
if left != null && right != null: // i.e. left, right are x, y
return node
// bubble up x or y
if left != null:
return left
if right != null:
return right
// x, y not in node's subtree
return null
Corner cases:
- When x or y is not present in tree, then throw (or lca is null).
- When x is ancestor of y, then lca is x.
- When x == y, then lca is x or y.
lca-bt-check(node, x, y): if node == null: throw if x == null || y == null: throw if x == y: if !is-present(node, x): throw return x // or y lca = lca-bt(node, x, y) if lca == null: throw // corner case when lca is x or y if lca == x && !is-present(lca, y) || lca == y && !is-present(lca, x): throw return lca
{Hat tip to ctci]
Using a parent pointer makes things easy, but typically parent pointer is not kept in the node.
ReplyDeleteThe solution for the same with ILLUSTRATIVE PICTURES and complete working code in Java at,
ReplyDeletehttp://technicalypto.blogspot.com/2010/02/find-common-parent-in-binary-search.html
50
ReplyDelete/ \
25 75
/
65
/
55
Will this algorithm work for LCA of 55 and 65?
@jimmy: yes.
ReplyDeletewhat if the parent link is not there??
ReplyDeleteLCA of a Binary Search Tree is easier as shown here,
ReplyDeletehttp://www.ritambhara.in/lowest-common-ancestor-in-binary-search-tree/
@kamal, the code you point out uses recursion instead of looping. compared to looping, recursion code is readable but also typically slower.
ReplyDelete