Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree#


Question Number Difficulty Tag Tag Tag Tag

Problem#

A clear and concise statement of the problem.

Example#

1tree_values = [4, 2, 1, None, None, 3, None, None, 7, None, None]
2root = build_binary_tree_from_list_preorder(tree_values)
3print_binary_tree(root, node_info=lambda n: (str(n.value), n.left, n.right), is_top=True)

    4
   / \
  2   7
 / \
1   3

Intuition#

Here are key observations that can be made about the problem:

  1. If \(p \leq r \leq q\) or \(q \leq r \leq p\), then \(r\) is the lowest common ancestor of \(p\) and \(q\).

    1. What this means is that if the very root node of the tree is between \(p\) and \(q\), then the root node is the lowest common ancestor.

    2. This observation stems from the fact that if \(p\) and \(q\) are on opposite sides of \(r\), then \(r\) is the lowest common ancestor. You can prove this by contradiction.

  2. Otherwise, if \(p < r\) and \(q < r\), then the lowest common ancestor of \(p\) and \(q\) is in the left subtree of \(r\).

    1. In fact you do not need to check both, just one is sufficient because of the first observation.

  3. Otherwise, if \(p > r\) and \(q > r\), then the lowest common ancestor of \(p\) and \(q\) is in the right subtree of \(r\).

    1. In fact you do not need to check both, just one is sufficient because of the first observation.

if not, p and q must either exist in left or right subtree of root. Now since the node can be its own ancestor it just needs us to find out the first encounter of p or q in the left or right subtree, once found that node is the LCA. Why? Because once you contain the problem to only left or right, assume without loss of generality that it is the left subtree, then the first encounter say it is \(p\), then we know that \(q\) must be somewhere below \(p\), so \(p\) is the lowest common ancestor of \(p\) and \(q\).

This is hinged upon the assumption \(p\) and \(q\) are in the tree (exists). See constraints.

Another part is

        if root == p or root == q:
            return root

How I arrived is base case, so initially the drill is if not root: return but here it is not case cause assumption says number of nodes is at least 2.

So I came up with this. And it turns out it also fulfills my logic on if we first encounter p or q in the left or right subtree, then that node is the LCA.

Assumptions#

List of any assumptions made in the problem solving process.

Constraints#

What are the Constraints for?#

Explanation of the constraints and their impact on the problem and solution.

Test Cases#

Set of test cases for validating the solution.

Edge Cases#

Discussion of any potential edge cases in the problem.

Walkthrough / Whiteboarding#

Detailed walkthrough of the problem-solving process.

Theoretical Best Time Complexity#

Discussion of the theoretical best time complexity for this problem.

Theoretical Best Space Complexity#

Discussion of the theoretical best space complexity for this problem.

Space-Time Tradeoff#

Analysis of the tradeoff between space and time complexity for the problem.

Solution (Potentially Multiple)#

Intuition#

Brief explanation of the core ideas or insights that form the basis for the solution.

Visualization#

Visual representation of the problem and solution (if applicable).

Algorithm#

Pseudocode#

Mathematical Representation#

Correctness Proof#

Implementation#

Tests#

Set of tests for validating the algorithm.

Time Complexity#

Analysis of the time complexity of the solution.

Space Complexity#

Input Space Complexity#

Analysis of the space complexity of the input.

Auxiliary Space Complexity#

Analysis of the space complexity excluding the input and output space.

Total Space Complexity#

Analysis of the total space complexity of the solution.

References and Further Readings#