Teaching Kids Programming – Recursive Algorithm to Find the Lowest Common Ancestor of a Binary 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.

Find the Lowest Common Ancestor of a Binary Tree via Recursion

If the root value is either p or q, then it must be the common ancestor of both p and q. Otherwise, we check recursively if the common ancestor if it is at the left tree, or if it is at right tree, otherwise, current node will be the common ancestor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 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':
        if root is None:
            return None
        if root.val == p.val or root.val == q.val:
            return root
        a = self.lowestCommonAncestor(root.left, p, q)
        b = self.lowestCommonAncestor(root.right, p, q)
        if a is None:
            return b
        if b is None:
            return a
        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':
        if root is None:
            return None
        if root.val == p.val or root.val == q.val:
            return root
        a = self.lowestCommonAncestor(root.left, p, q)
        b = self.lowestCommonAncestor(root.right, p, q)
        if a is None:
            return b
        if b is None:
            return a
        return root

Recursive algorithm above to find the common ancestor takes O(N) time as we need to traverse the binary tree and there are N nodes. The space complexity is O(H) as we are implicitly using stack due to recursion and H in the worst case is N – considering a binary tree highly degraded/imblanced to a linked list.

We can also traverse upwards from p or q to the roots (which requires a Depth First Search or Breadth First Search to construct the link from children nodes to parent nodes), and then store the seen nodes along the way. And when we traverse from another given node, the first node that is seen is the lowest common ancestor: Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree.

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) —