Finding the lowest common ancestor a binary search tree (Google interview question)

Summary

The article discusses the algorithm for finding the lowest common ancestor (LCA) in a binary search tree (BST), a common problem in technical interviews at top tech companies like Google and Facebook.

Abstract

The article titled "Finding the lowest common ancestor in a binary search tree" is a guide addressing a frequently encountered problem in software engineering interviews. The author explains the concept of the lowest common ancestor (LCA) in the context of a binary search tree (BST) and provides a link to the problem statement on LeetCode. The LCA is the lowest node in the tree that has both given nodes as descendants. The author emphasizes the inherent properties of a BST that make the problem easier than if it were a binary tree, noting that for any node in a BST, all values to the left are smaller, and all values to the right are larger. The solution involves a recursive approach, where the search for the LCA depends on the comparison of the given nodes' values with the current node's value. If both nodes are smaller, the search continues to the left; if both are larger, it goes to the right. Otherwise, the current node is the LCA. The article includes illustrations to aid understanding and invites readers to ask questions or request solutions to other problems. The author also encourages readers to follow their Medium profile for more content on software engineering interviews and coding questions.

Opinions

The author believes that understanding the properties of a binary search tree is crucial for solving the LCA problem efficiently.
Recursion is highlighted as a key technique for solving tree-related problems, including the LCA challenge.
The author suggests that the LCA problem is simpler in a BST compared to a regular binary tree due to the BST's ordered structure.
Engagement with the audience is encouraged, as the author invites questions and suggestions for future articles.
The article promotes the author's Medium profile, indicating a self-marketing strategy and a commitment to providing ongoing educational content in the field of software engineering.

Finding the lowest common ancestor a binary search tree (Google interview question)

Hey all! This problem is a commonly asked question at Google, Facebook, and other top tech companies, so I wanted to go over it.

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

For example, given 2 and 4, the lowest common ancestor is 2.

Given 4 and 7, the lowest common ancestor is 6.

Given 7 and 9, the lowest common ancestor is 8.

Now this problem is a bit easier than if we were given a binary *tree*, instead of a binary *search* tree. Binary *search* trees have a nice property that for a given node, everything to the left of the node is smaller than the given node’s value, and everything to the right is greater than it. Let’s take advantage of that property. But first…

Tree problems, recursion. Tree problems, recursion. Tree problems, recursion. Get that in your head!!!

Let’s think about what we would want to do given any node.

1/ If p and q are smaller than the given node’s value, we know the ancestor must be to the left.

2/ If p and q are both larger than the given node’s value, we know the ancestor must be to the right.

3/ Else, meaning the p < node’s value < q, or p is the node or q is the node, we just return the node.

Let me know if you have any questions or if there’s another problem you want me to solve!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!