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:
- search (DFS/BFS) the two nodes x and y to get their paths in O(n) time OR 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
class Node:
int value
Node left
Node right
Node parent
class ListNode:
Node value //Node is Binary Tree node
ListNode next
Node getLCA_BT(Node root, Node x, Node y):
ListNode lx = getPath(x)
ListNode ly = getPath(y)
return getLCAFromPaths(lx, ly)
ListNode getPath(Node n):
ListNode ln = null
ListNode after = null
while (n != null):
ln = new ListNode()
ln.value = n
ln.next = after
after = ln
n = n.parent
return ln
Node getLCAFromPaths(ListNode lx, ListNode ly):
Node lca = null
while (lx.value == ly.value): // lx.value.value
lca = lx.value //or ly.value
lx = lx.next
ly = ly.next
return lca
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):
Node lca, x, y = null
do:
lca = x //or y
x = sx.pop()
y = sy.pop()
while (x == y)
return lca
[Hat tip to B.]
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