**search**tree (BST) is simple. For any nodes x and y, the LCA is the first node which lies between x and y starting from root.

```
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): 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.]

**Without parent node:**

Check to see if both nodes are present in current node's subtree and return null if not. Check left and right subtrees. If both nodes are not present in either left or right subtrees, then current node is lca. Bubble up lca.

lca-bt-check(node, x, y): if node == null: throw if x == null || y == null: throw if !is-present(node, x) || !is-present(node, y): throw return lca-bt(node, x, y) // inefficient lca-bt(node, x, y): if node == null: return null if !is-present(node, x) || !is-present(node, y) return null left = lca-bt(node.left, x, y) if left != null: return left right = lca-bt(node.right, x, y) if right != null: return right return node 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 tactic. 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 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

{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