DAY 9   /   TODAY’S CHALLENGE

Lowest Common Ancestor

Take a moment to find your approach. Then put it to the test.

Prefer learning on the site? Open this challenge →

In the official React documentation, it's recommended that to find out where state data should live, the following steps be taken:

• Identify every component that renders something based on that state.
• Find a common owner component (a single component above all the components that need the state in the hierarchy).
• Either the common owner or another component higher up in the hierarchy should own the state.

This is an algorithmic problem-- let's find the lowest common ancestor!

You're given a binary search tree tree1 and two of its child nodes as parameters. Can you write a method lowestCommonAncestor(root: Node, node1: Node, node2: Node) to identify the lowest common ancestor of the two nodes? The lowest common ancestor is the deepest node that has both of the two nodes as descendants.

In the below example, the lowest common ancestor of node 5 and 8 is 7.

/*
       7
      / \
     4   8
    / \
   1   5
*/

The method will called in the following manner: lowestCommonAncestor(root, node1, node2);.

You can assume our standard node definition for the tree vertices:

// Node definition
function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

# Node definition
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Bonus: is there a way to find the lowest common ancestor of two nodes if the root wasn't passed as a parameter?

Constraints

• Number of nodes in the BST

Already seen this topic? Change your newsletter or starting day to pick up where you want.

YOUR NEXT STEP / ALGODAILY PREMIUM

Turn a daily habit into deeper preparation.

Unlock the learning library: visual lessons, coding challenges, quizzes, and videos across algorithms, system design, frontend, and more.

Get AI tutoring, save notes, track applications, and take your learning offline with the AlgoDaily books.

Prefer a book? Browse The AlgoDaily Book: Core Essentials.

Small, consistent practice adds up. If today’s idea helped, forward this email to a friend who’s preparing for their next opportunity.

Keep learning,
Jake
Founder, AlgoDaily

““If you are insecure, guess what? The rest of the world is, too. Do not overestimate the competition and underestimate yourself. You are better than you think.””
— Tim Ferriss