Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in JavaScript

Lowest Common Ancestor of a Binary Tree

Explore how to find the lowest common ancestor of two nodes in a binary tree. Understand the problem constraints, apply depth-first search, and implement a solution to identify the ancestor node correctly.

We'll cover the following...

Statement

Given the root node of a binary tree with nn nodes, your task is to find the lowest common ancestor of two of its nodes, p and q.

Note: The lowest common ancestor of two nodes, p and q, is defined as the lowest node in the binary tree that has both p and q as descendants.

A node can also be a descendant of itself. For example, if q is a descendant of p, and we know that p is a descendant of itself, then p will be the lowest common ancestor of p and q.

Constraints:

  • 2≤n≤5002 \leq n \leq 500
  • All Node.data are unique.
  • p !=!= q
  • p and q exist in the tree.

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Lowest Common Ancestor in a Binary Tree

1.

What is the lowest common ancestor of 88 and 66 in the following binary tree?

  5
 / \
6   7
   / \
  8   9
A.

5

B.

6

C.

7

D.

8

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5
6

Try it yourself

Implement your solution in the following coding playground.

JavaScript
usercode > LowestCommonAncestor.js
// Definition of a binary tree node
// class TreeNode {
//   constructor(data) {
//     this.data = data;
//     this.left = null;
//     this.right = null;
//   }
// }
import {TreeNode} from './ds_v1/BinaryTree.js';
class Solution {
    lowestCommonAncestor(root, p, q) {
        
        // Replace this placeholder return statement with your code
        return null;
    }
}
export default Solution;
Lowest Common Ancestor of a Binary Tree