## ALGODAILY

August 12, 2024

“A person's success in life can usually be measured by the number of uncomfortable conversations he or she is willing to have.”

- Tim Ferriss

#### Day 9: Lowest Common Ancestor

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`.

SNIPPET
``````/*
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:

js
``````// Node definition
function Node(val) {
this.val = val;
this.left = this.right = null;
}``````
py
``````# 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 <= `1000`
• The nodes will always contain integer values between `-1000000000` and `1000000000`
• Expected time complexity : `O(n)`
• Expected space complexity : `O(1)`

Get the Solution →

Have you seen this question before? We are frequently adding problems and may have updated the order. You can change the day that you're on in the settings panel. As always, you can see the solution and a full step by step explanation at this link.

Love the daily emails? AlgoDaily exists to provide hand-held coding interview coaching and career resources to developers from non-traditional paths. With premium, now on sale, you'll get:

• Unlimited access to all courses and materials, spanning Data Structures and Algorithms, Systems Design, OOP, Frontend, Machine Learning, and much more!
• Access to 700+ lessons and challenges, 2000+ diagrams and illustrations, 700+ quizzes, and 10+ hours of video
• AI Private Tutor trained on AlgoDaily
• Customize your AlgoDaily newsletter by switching to another crash course newsletter, and choosing the day you're on
• Technical interview or career building courses and tutorials added monthly
• Bulk export all of your completed solutions, access the notes tool, track job applications, and see all community submissions
• Bonus: PDF, Mobi, and ePub copies of The AlgoDaily Book: Core Essentials (a \$29 value)