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

Lowest Common Ancestor of a Binary Tree

Explore how to determine the lowest common ancestor of two nodes in a binary tree. This lesson helps you understand the problem constraints, definition, and approach using depth-first search strategies. By mastering this, you will improve your ability to solve binary tree problems efficiently in coding interviews.

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.

Go
usercode > LowestCommonAncestor.go
// Definition of a binary tree node 
// type TreeNode[T any] struct {
// 	Data  T
// 	Left  *TreeNode[T]
// 	Right *TreeNode[T]
// }
package main
import (. "golang-test-code/ds_v1/BinaryTree") // TreeNode[T]
type Solution struct {
	lca *TreeNode[int]
}
func (s *Solution) lowestCommonAncestor(root, p, q *TreeNode[int]) *TreeNode[int] {
	
    // Replace this placeholder return statement with your code
    return nil
}
Lowest Common Ancestor of a Binary Tree