# Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree

Teaching Kids ProgrammingVideos on Data Structures and Algorithms

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5]p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5]p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:
Input: root = [2,1]p = 2, q = 1
Output: 2

Constraints:
The number of nodes in the tree is in the range [2, 105].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the BST.

### Algorithms to Find the Lowest Common Ancestor of a Binary Tree

Given a general Binary Tree, we can apply the Recursive Algorithm (Teaching Kids Programming – Recursive Algorithm to Find the Lowest Common Ancestor of a Binary Search Tree) to solve this problem:

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         def f(root, p, q):             if not root:                 return             if root.val == p.val or root.val == q.val:                 return root             a = f(root.left, p, q)             b = f(root.right, p, q)             if not a:                 return b             if not b:                 return a             return root                 return f(root, p, q)```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def f(root, p, q):
if not root:
return
if root.val == p.val or root.val == q.val:
return root
a = f(root.left, p, q)
b = f(root.right, p, q)
if not a:
return b
if not b:
return a
return root

return f(root, p, q)```

If a root is either p or q, then it is the lowest common ancestor since a node is a common ancestor (or descendant) of itself. Then, we try to find the ancestor in the left tree, if we can’t find it, it is somewhere in the right tree and vice versa. Otherwise, the p and q are separate in left and right tree, in which case the root is the lowest common ancestor.

Another way is to perform a Depth First Search or Breadth First Search algorithm to remember the parent nodes for each node in a hash table – which allows us to traverse from descendant node p or q upwards to the root). Then, we need to remember the seen nodes in a hash set, and when we traverse from another given node, the first node that has been seen is the lowest common ancestor.

 ```1 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 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         parent = {}         def dfs(root, par):             nonlocal parent             if not root:                 return             dfs(root.left, root)             dfs(root.right, root)                         parent[root] = par                     dfs(root, None)         seen = set()                 while p:                   seen.add(p)                         p = parent[p]                 while q:             if q in seen:                 return q             q = parent[q]         return None```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
parent = {}
def dfs(root, par):
nonlocal parent
if not root:
return
dfs(root.left, root)
dfs(root.right, root)
parent[root] = par

dfs(root, None)
seen = set()

while p:
p = parent[p]

while q:
if q in seen:
return q
q = parent[q]
return None```

The time and space complexity is O(N) where N is the number of nodes in the given binary tree.

### Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree

If the binary tree is also a Binary Search Tree, then we can utilise the fact that the left nodes are strictly smaller and the right nodes are strict larger. When p and q are smaller than root, then the lowest common ancestor is somewhere on the left tree, and when p and q are larger than root, then the lowest common ancestor is somewhere on the right tree. Otherwise, the root is the lowest common ancestor (since p and q are separate in left/right tree respectively).

We can do this Recursion (beaware of Stack Overflow risk):

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         def g(root, p, q):             if not root:                 return             if root.val < p.val and root.val < q.val:                 return g(root.right, p, q)             if root.val > p.val and root.val > q.val:                 return g(root.left, p, q)             return root         return g(root, p, q)```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def g(root, p, q):
if not root:
return
if root.val < p.val and root.val < q.val:
return g(root.right, p, q)
if root.val > p.val and root.val > q.val:
return g(root.left, p, q)
return root
return g(root, p, q)```

We can do this iteratively by moving the current pointer to left or right. The time complexity is O(H) where H is the height of the binary search tree and in worst case H is N – the number of nodes.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ```# Definition for a binary tree node. # class TreeNode: #     def __init__(self, x): #         self.val = x #         self.left = None #         self.right = None class Solution:     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':         while root:             if p.val < root.val and q.val < root.val:                 root = root.left             elif p.val > root.val and q.val > root.val:                 root = root.right             else:                 break         return root```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
break
return root```

#### Algorithms to Find the Lowest Common Ancestor of a Binary (Search) Tree

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating