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

Lowest Common Ancestor of a Binary Tree

Understand how to identify the lowest common ancestor of two given nodes in a binary tree. Learn to apply depth-first search traversal techniques and logical reasoning to solve the problem efficiently within the constraints of unique node data and the presence of both nodes.

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.

C++
usercode > LowestCommonAncestor.cpp
// Definition for a binary tree node
// template<class T>
// class TreeNode {
// public:
//     T data;
//     TreeNode<T>* left;
//     TreeNode<T>* right;
//     TreeNode(const T data) : data(data), left(nullptr), right(nullptr) {}
// };
class Solution {
    public:
        TreeNode<int>* LowestCommonAncestor(TreeNode<int>* root, TreeNode<int>* p, TreeNode<int>* q) {
            
            // Replace this placeholder return statement with your code
            return nullptr;
        }
};
Lowest Common Ancestor of a Binary Tree