Summary

The website content outlines two methods for finding the lowest common ancestor (LCA) in a binary tree, a problem frequently encountered in Facebook technical interviews.

Abstract

The article discusses two approaches to solving the problem of finding the lowest common ancestor (LCA) of two given nodes in a binary tree, a common technical interview question at Facebook. The first solution involves creating a parent map by traversing the tree and storing the ancestors of each node. By checking if the ancestors of one node are present in the set of ancestors of the other node, the LCA can be determined. This method has a time complexity of O(N) and a space complexity of O(N) due to the storage of the parent map. The second solution employs recursion, where a function is called at each node to determine if the current node is the LCA based on the presence of the target nodes in its left and right subtrees. This recursive approach also has a time complexity of O(N) and a space complexity of O(N) attributed to the call stack. The article provides code snippets for both solutions and encourages readers to follow the author for more software engineering interview guides and coding tips.

Opinions

The author suggests that building a map of parents is an effective way to find the LCA, emphasizing the importance of traversing the tree to gather information about node relationships.
The recursive solution is presented as an alternative that leverages logic applied at each node to propagate the LCA value upwards, indicating a preference for elegant, in-place algorithms.
The article implies that understanding both iterative and recursive approaches to tree problems is crucial for technical interviews, highlighting the need for versatility in problem-solving techniques.
By providing code examples and complexity analysis, the author demonstrates a commitment to comprehensive explanations and educational value, aiming to prepare candidates thoroughly for interview questions.
The invitation to follow the author and the mention of membership suggests that the author values community engagement and continuous learning within the field of software engineering.

Common Facebook Interview Question: Lowest Common Ancestor

We’ll go through two ways to solve this common problem asked at Facebook.

Question

Here’s the question:

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

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).”

As an example, if we’re given this tree, and p=1 and q=5 , then our answer will be 3.

First solution: Parent Map

Intuition

We know that we’ll have to first find both of the nodes. What if we built a map of the *parents* of the nodes?

e.g., for node p, if we could traverse upwards from p to the root of the tree, then for each node along the way, we can just see if it’s in the set of ancestors of q.

So we can start with a typical tree traversal function, which takes as input a current node, but also a parent node. We call this on the root node to build our parent map.

After building the parent map, we can add all the ancestors of p into a set.

Then, we traverse upwards, starting from q. If the next ancestor is in the set of p’s ancestors, then we return that node! Because we’re traversing upwards, we know that the first node that is also in p’s ancestor list must be the lowest common ancestor.

Here’s the code:

Algorithmic Complexity

The runtime here is O(N) — we do three traversals though!

The space complexity is also O(N) to store the parent map.

Second solution: Recursion

Intuition

We’ll come up with some logic to use at *every node*, so that when we do find the lowest common ancestor, we’ll be propagate that value up.

Let’s think through the conditions:

1/ If our current node is p or q, then we return the current node.

2/ If our current node doesn’t exist, we return None.

Let’s call our function recursively on node.left (call this value “left”) and node.right (call this value “right”).

3/ If left and right both exist, then we know our current node must be the lowest common ancestor.

4/ If left exists, but not right, return left.

5/ If right exists, but not left, return right.

1/ and 2/ are straightforward.

3/ we know that if one node is on the left, and one node is on the right, we should return our current node.

4/ means we found the lowest common ancestor on the left, and the answer is what was returned from 1/ or 3/, or passed up from another case of 4/ or 5/.

5/ Same as 4/, but for the right node.

Here’s the code:

The runtime here is O(N). We do need to do one traversal!

The space complexity is O(N), for the recursive call stack.

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!