Introduction
Daniel (🧔🏽♂️) nodded his head slowly as he added cream to his freshly poured coffee. He had worked hard to learn his Leetcode and he was feeling ready. He took a sip and walked over to his laptop and sat down. Moments later the interview began.
👩 “Good afternoon Daniel! Thanks for taking the time to interview with me today. Let’s begin with some brief introductions. My name is Jordanna! I’m a senior engineer on the user performance improvement team and I will be conducting your coding interview today.”
🧔🏽♂️ “Thank you for this opportunity, I’m looking forward to it. I graduated with a B.Sc. in civil engineering from UTSA two years ago and I’ve spent the last year and a half working DuBank as a junior software engineer.”
👩 “It’s a pleasure to meet you Daniel. Let’s dive into this.” Jordanna (👩 ) copied the problem into the shared code editor and Daniel reads the problem statement as he takes a slow sip of his refreshing medium roast.
Problem Statement
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).”
Example 1:
3
5 1
6 2 0 8
7 4
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
3
5 1
6 2 0 8
7 4
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5,
since a node can be a descendant of itself
according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
🧔🏽♂️ “We are given a binary tree and we are asked to find the lowest common ancestor. If I understand correctly, this is not a binary search tree, am I correct?”
👩 “Yes, as we can see in the examples, the nodes are not sorted.”
🧔🏽♂️ “What is the range on the number of nodes that we can expect to see?”
👩 “We can expect anywhere from 2 to 10,000 nodes.”
🧔🏽♂️ ”Are all node values unique?”
👩 “Yes, all node values are unique.”
🧔🏽♂️ “Can we ever have a case where p and q are equal?”
👩 “No, p will never be equal to q.”
🧔🏽♂️ “Ok, thanks! That helps. If we look at the root node of the tree, there are three different case that we need to account for. One: both nodes p and q could be in there left subtree, Two: one node could be in the left subtree and the other could be in the right subtree. Three: both nodes could be in the right subtree. Would you say that I have accurately described the different scenarios?”
👩 “I like where you are going with this, Daniel! It’s a good start. Are there any other cases that you can think of?”
🧔🏽♂️ “Let me scan the problem statement again… Ah, yes! The LCA could be one of the nodes. We could have a case where p is a direct ancestor of q or vice versa. I believe this expands upon cases one and three. Would you say that my articulation of the problem is correct? ”
👩 “Yes, it sounds like you’re ready to start coming up with a solution. How would you write this up?””
🧔🏽♂️ “Thanks Jordanna, I’d love to! Since this is a tree traversal problem, it can be solved using recursion. Since I’ll be using Python, I’ll need to be mindful of the recursion limit. By default, the recursion limit in Python is typically set to 1,000. I’ll begin by setting it to 20,000 at the beginning of my solution and I’ll change it back at the end. Are you ok with this approach?”
👩 “Yes, so far so good. How would you write the recursive algorithm?”
🧔🏽♂️ “At every node, we will recursively traverse down the left subtree and then down the right. When we reach the leftmost leaf node, the next left subtree recursive call will return None and the next right subtree recursive call will return None. We can use left and right variables to keep track of these returned values.”
👩 Jordanna nodded her head in agreement.
🧔🏽♂️ “If the root value equals that of p or q, we return the root address up the to the next stack frame. If left and right are not None, we have found our LCA and return root. At this point in the else if, we only have two options remaining. If left is not None, we return left, otherwise we return right.” Daniel paused for a moment, and continued. “If p or q was found in the right subtree, right will equal the node’s memory address, otherwise, we will return None. As this algorithm runs it course, the LCA node address will be returned all of the way up to the top stack frame until it is return to the original caller.”
Recursive Solution (p & q exist)
🧔🏽♂️ Daniel wrote the following code and made sure to add comments as we went along. He then ran through an example input and validated the results.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""
Time: O(N)
Space: O(N)
"""
if not root:
return None
# Recursively search through the left and then the right branches
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# return the answer ~ last call
if root.val == p.val or root.val == q.val:
# Return the node when we find it
return root
elif left and right:
# If left and right are not None, we have found
# the LCA. Return it up to the next stack frame.
return root
elif left:
# Since p or q was found in the left subtree,
# return it up the call stack.
return left
else:
# if p or q was found in the right subtree,
# it will be returned up, if neither were
# found, we will return None. This means that
# we have not found either or our target nodes
# yet.
return right
Recursive solution (p or q may not exist)
👩 “Daniel this looking good! As a follow-up. Let’s say that we no longer can guarantee that both p and q exist in the binary tree. How would this change your solution?”
🧔🏽♂️ “Ok, let’s see…” Daniel took a moment and reviewed his solution and continued. “If we don’t have two target nodes in the binary tree, my current solution will return the memory address of the one node we did find. I can see how this could cause problems. If a valid LCA does not exist in the tree, I would expect a None response. I believe we will need to keep track of the number nodes that have been found. Am I on the right track?”
👩 “Yes, you’re on the right track. Please continue.”
🧔🏽♂️ “I’m thinking we can traverse through the binary tree in the same way we did in the original solution. Only this time we’ll use a traverse(...,ans:TreeNode=None) function with a default parameter to keep track of the LCA node. This function will return a (flag, ans) tuple. We can use left and right variables to keep track of the left and right subtree search result flags. If we find p or q at a node, we will return a tuple with the flag and None (1, None). After we traverse the left and right subtrees for each node, we can set flag = 0 for that node and then check if we have found the LCA. Jordanna, do you have any comments or concerns with where I’m going with this?”
👩 “So far so good Daniel.”
🧔🏽♂️ “Ok, if the current node is equal to either p or q, we will set flag = 1. After that, we can sum up the flags and see if we have found the LCA yet. If (left = 1) or (right = 1) and flag = 1, we will set ans = node. If (left = 1) and (right = 1) and flag = 0, we will set ans = node. Once we have found the LCA, left + flag + right will equal 1 and ans will equal the LCA node for the remainder of the recursive calls. The ans will be returned through the call stack up to the top and returned to the original caller. If we only ever find 1 target node, we will never set the ans to a node memory address and will eventually return None as our final answer."
👩 “We still have some time left here, can you please code it up for me?”
🧔🏽♂️ “For sure!" Daniel responded cheerfully and hammered out the solution below."
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from typing import Tuple
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traverse(node: TreeNode, p: TreeNode, q:TreeNode, ans: TreeNode = None) -> Tuple[Any]:
"""
Time: O(N)
Space: O(N)
"""
if not node:
return 0, ans
# Post order traversal through binary tree
left, ans = traverse(node.left, p, q, ans = ans)
right, ans = traverse(node.right, p, q, ans = ans)
flag = 0
# Set flag = 1 if p or q found
if node.val == p.val or node.val == q.val:
flag = 1
# The sum of the flags will be greater
# than 1 if p & q have been found
if left + flag + right == 2:
ans = node
# If p or q found in a subtree or
# the current node, return 1
if left or flag or right:
return 1, ans
else:
return 0, ans
_, ans = traverse(root, p, q)
return ans
👩 “Can you run through an example for me?”
🧔🏽♂️ “Are you ok with me pointing my camera towards my sheet of paper here so that I can draw a tree and run through an example?”
👩 “Yes, for sure!”
🧔🏽♂️ Daniel worked through an example and validated his solution.
👩 After reviewing Daniel’s solution, Jordanna closed the meeting: “Thanks for taking the time interview with me today!”
🧔🏽♂️ “Thanks Jordanna, have a great afternoon!”
👩 “You’re welcome Daniel! You too!”