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

Teaching Kids Programming: Videos 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:      
            seen.add(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

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

–EOF (The Ultimate Computing & Technology Blog) —