Lowest Common Ancestor of a Binary Search Tree

Finding the lowest common ancestor (LCA) in a Binary Search Tree (BST) takes advantage of the properties of a BST, where nodes to the left are smaller and nodes to the right are larger.

Here’s a simple approach to find the LCA:

Start at the Root: Begin the search from the root node of the BST.
Compare Values:
- If both p and q are less than the root’s value, then the LCA must be on the left side of the tree.
- If both p and q are greater than the root’s value, then the LCA must be on the right side of the tree.
- If p and q are on different sides of the root, then the current root is the LCA.
Continue the Search: Based on the comparison, move to the left or right child and repeat step 2.
Return the LCA: When the LCA is found, return the node.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            # If both p and q are to the left of the root, move to the left
            if p.val < root.val and q.val < root.val:
                root = root.left
            # If both p and q are to the right of the root, move to the right
            elif p.val > root.val and q.val > root.val:
                root = root.right
            # If p and q are on different sides of the root, then this root is the LCA
            else:
                return root
        return None

This code uses a while loop to traverse the tree based on the values of p and q. It returns the LCA node when found. The efficiency of this code is good due to the properties of the BST, with a time complexity of O(log n) in a balanced tree or O(n) in the worst case.

Here is an Python implementation to find the lowest common ancestor (LCA) of two given nodes p and q in a binary search tree (BST):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        curr = root
        
        while curr:
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left 
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
            else:
                return curr

The key ideas are:

Traverse the tree starting from the root node.
If both p and q are less than the current node, go left.
If both are greater, go right.
Otherwise, the current node is the LCA.

This leverages the BST property that left subtree nodes are <= parent and right subtree nodes are >= parent. By comparing p and q to the current node, we can iteratively narrow down the search space.

Time complexity is O(h) where h is the tree height, since in the worst case we traverse the height of the tree. Space is O(1).

LCA is a common node of any child nodes. Example 1 illustrates this part. A node can be a child of itself. Example 2 illustrates this part.

Can we consider it as the first common parent? Yes. We look at the immediate common parent.

Binary Search Tree We can search for p and q in log n time using binary search.

The lowest common ancestor (LCA) of two nodes in a tree is the lowest (farthest from the root) node that has both of the two nodes as descendants.

In simpler terms, if you traverse up the tree from each of the two nodes, the lowest common ancestor is the first common node that both paths intersect at.

Some key properties:

The LCA is the shared parent node closest to (or at) the leaves.
Every ancestor of the two nodes is also an ancestor of their LCA.
The LCA may be one of the two nodes itself if one is a descendant of the other.
In a binary search tree, the LCA can be found efficiently by traversing up and comparing node values.

So in plain language, the lowest common ancestor is the first parent node that the two nodes have in common when you traverse up the branches towards the root. It’s the deepest shared relative of the two nodes.

Define the Interface

Input: root (BST root object), p & q (node objects) Output: treenode object (lca)

Analyze the Input and Output

Here is an analysis of the inputs and outputs for the binary search tree lowest common ancestor algorithm:

Input:

root - The root node of the binary search tree
p - One of the two nodes whose lowest common ancestor we want to find
q - The other node whose lowest common ancestor we want to find

Output:

The lowest common ancestor (LCA) node of p and q in the tree

Input Constraints:

Tree contains between 2 and 100,000 nodes
Node values are unique integers between -10^9 and 10^9
p and q will exist somewhere in the tree
p != q (they won’t be the same node)

Output Characteristics:

The LCA will be a node in the tree (not null)
It will be an ancestor of both p and q
There will only be one unique LCA node for any valid p and q
It will be the deepest/farthest node from the root that is an ancestor of both
For BSTs, it can be found in O(h) time and O(1) space where h is tree height

So in summary, the algorithm takes a BST root and two child nodes, leverages BST structure to efficiently prune the search space in halves, and returns their unique lowest common ancestor node.

Identify the Invariant

The invariant in the binary search tree lowest common ancestor algorithm is:

When traversing up the tree from the root, following left/right branches based on comparing node values to p and q, the current node is guaranteed to be an ancestor of both p and q.

Specifically:

If both p and q are less than curr, then curr and everything in curr’s right subtree cannot be the LCA.
If both p and q are greater than curr, then curr and everything in curr’s left subtree cannot be the LCA.
Therefore, by recursively eliminating half the remaining tree, we maintain the invariant that curr is an ancestor of p and q until it reaches their lowest common ancestor.

The key insight is that BST structure allows us to prune the search space in half each step. We leverage the ordering of BST nodes to prune left or right halves.

As long as we recursively compare p and q to curr, splitting left or right accordingly, we are guaranteed the invariant holds true - curr is an ancestor of both nodes. When we can no longer split, curr must be the deepest common ancestor.

Identify the constraints

The number of nodes in the tree is in the range [2, 10^5].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the BST.

Search the Problem Space Take advantage of the BST property to search for p and q.

Classify the Problem

The problem of finding the lowest common ancestor (LCA) of two nodes in a binary search tree can be classified as:

Tree-based algorithm
Graph algorithm
Search problem
Optimization problem

More specifically:

It involves traversing a tree data structure to find the optimal LCA node.
It can be modeled as a graph search algorithm on the tree.
We are searching for the common node that satisfies the criteria of being the lowest/deepest one.
It is an optimization problem because we want to find the lowest (farthest from root) ancestor that satisfies the common ancestor criteria.

Some other key attributes:

Leverages ordering and structure of binary search trees
Divide and conquer approach to prune search space
Efficient O(h) time and O(1) space complexity
Deterministic algorithm with a single optimal solution
Read-only query, does not modify the tree

So in summary, this is an efficient tree-based search and optimization algorithm that finds the optimal lowest common ancestor node for two descendants in a binary search tree. It leverages the innate properties of BSTs to optimize the search through pruning.

BST Traversal

Analyze the Examples

Let’s analyze the examples provided for finding the lowest common ancestor (LCA) in a binary search tree:

Example 1:

Tree with nodes values 6,2,8,0,4,7,9,3,5
p = node 2
q = node 8
LCA is node 6

This makes sense since:

Node 2 is in the left subtree of 6
Node 8 is in the right subtree of 6
6 is the deepest node that is an ancestor of both 2 and 8

Example 2:

Same tree
p = node 2
q = node 4
LCA is node 2

This is correct because:

Node 4 is in node 2’s left subtree
A node is considered its own descendant
Therefore, the deepest common node is 2 itself

Example 3:

Simple tree with just nodes 2 and 1
p = 2, q = 1
LCA is node 2

Again this is correct since:

Node 1 is in node 2’s left subtree
Node 2 is the only ancestor of both nodes
So the LCA has to be node 2

In all cases, the provided LCA matches the expected output based on the relative positions of nodes p and q in the tree. The examples demonstrate different possible tree structures and relative placements of the descendant nodes.

Case 1: Example 1 p is in the left subtree q is in the right subtree

Case 2: Example 2 p is in the left subtree q is in the left subtree

Case 3: Example 3 p is the root q is in left subtree

Example 1: Parent is common to both p and q parent of p is 6 parent of q is 6 Return the common parent.

Example 2: One of the node’s parent is itself parent of p is 6 parent of q is 4 (parent of q is p) Return the p as the lca

Example 3: One of the node is the root parent of p is itself parent of q is p Return the p as the lca

Example 4: Extend example 2, p = 4, q = 7 Parent of p is 2 Parent of q is 8 They are not common. We go back up one level, and find the parent common to both nodes (this is when the grandparent becomes the lca)

Locate p Based on p, try to locate q

Solve the Problem by Hand

Let’s solve an example by hand to find the lowest common ancestor (LCA) of two nodes in a binary search tree (BST):

         6
       /   \
      2     8
     / \   / \
    0   4 7   9
         / \
        3   5

And let’s say we want to find the LCA of nodes p = 2 and q = 9.

Here are the steps to solve this manually:

Start at the root node, which is 6.
Compare p and q values to the current node.
- p (which is 2) is less than 6.
- q (which is 9) is greater than 6.
This means the LCA must be in the left subtree of 6 since p is there. Go left to 2.
Now compare p and q to 2.
- p (which is 2) is equal to the current node.
- q (which is 9) is still greater.
Since one of the nodes equals the current node, we have found the LCA at 2.

Therefore, the LCA of nodes 2 and 9 is node 2.

We iteratively narrowed down the search space by branching left or right based on comparing p and q to current node. This allowed us to efficiently find the common ancestor without traversing the entire tree.

Describe the Pattern

Here is how I would describe the general pattern behind finding the lowest common ancestor in a binary search tree:

The algorithm relies on efficiently narrowing down where the LCA could be based on how the binary search tree imposes an ordering on the nodes.

Specifically:

Start at the root and set the current node to be the root.
Compare the values of nodes p and q to the value of the current node.
If both p and q are less than the current node, the LCA must be in the left subtree of the current node. Thus, recursively search the left subtree by setting the current node to be the left child.
If both p and q are greater than the current node, the LCA must be in the right subtree. Thus, search the right subtree by setting the current node to the right child.
If neither case is true, meaning the values split or one equals the current node, then the current node is the LCA.

This pattern of narrowing the search space by checking if p and q are both less than or greater than the current node leverages the ordering imposed by the BST structure. We eliminate roughly half the remaining tree from consideration each step.

The recursion continues until the LCA is found, which is guaranteed to occur in at most height iterations since one side will be eliminated each step. We leverage the ordering and hierarchical nature of BSTs to efficiently search without traversing the entire tree.

Yes, the pattern I described for finding the lowest common ancestor in a binary search tree matches the process we used to solve the problem manually.

When we solved the example by hand, we started at the root node and compared the values of nodes p and q to the current node value. Since p was less than the current node, but q was greater, we determined the LCA must be in the left subtree.

We recursively repeated this process of checking if both p and q were less than or greater than the current node to narrow down the search space. We went left once since p was less than the initial current node.

Then when we arrived at node 2, one of the target nodes matched the current node. At that point, we had found the LCA.

This aligns with the general pattern of leveraging the BST node ordering to eliminate subtrees from consideration and recursively search downwards until the LCA is found.

By manually working through the example, we mirrored the high-level approach of pruning the search space in half each step by checking if both nodes are less or greater than the current node. This pattern was reflected in the manual worked example.

Distill the Observations to Create Insights

Here are some key insights distilled from the observations of the binary search tree lowest common ancestor algorithm examples and analysis:

The relative positions of nodes p and q determine the LCA. It will be the first common ancestor reached when traversing up both paths from p and q.
The LCA node’s value will be bounded between the values of p and q in a BST due to the ordering of nodes. This allows us to eliminate subtrees during search.
Comparing p and q to the current node and branching left/right based on their values elegantly prunes the search space in half each iteration.
A node can be its own ancestor/descendant. The LCA could be one of p or q themselves if one is in the subtree of the other.
The optimal efficiency of O(h) relies on the BST structure. It ensures we prune ineffective branches and do not have to backtrack.
Performance is tied to tree height/balance. In worst case skewed trees, it could degrade to O(n).
We get single optimal LCA due to BST ordering. No backtracking or duplicate checking needed.

In summary, the key insights are around how BST structure enables pruning the search space in half each step, and that the LCA node’s value will be bounded between p and q’s values. This allows an efficient, single-pass algorithm without needing general graph traversal techniques.

If one of the node is the parent of the other. Return the parent If both the nodes have a common parent Return the common parent.

Brute Force Approach

Yes, there is a brute force approach to finding the lowest common ancestor (LCA) of two nodes p and q in a binary tree:

Traverse the entire tree depth-first, recording all ancestors of node p in a set/list.
Similarly traverse again to record all ancestors of node q in a set/list.
Find the common ancestors by taking the intersection of the two sets.
The lowest (farthest from the root) ancestor in the intersection is the LCA.

The time complexity of this algorithm is O(n) since in the worst case we have to traverse the entire tree twice to find all ancestors of p and q separately.

We also use O(n) space to store the ancestor sets. The space could be optimized to O(h) by only storing ancestors along a single path, but time remains O(n).

The key downsides are:

Repeated work traversing the entire tree for each node.
No early stopping when LCA is found.
More complex logic required to track ancestor sets.

So in summary, a brute force approach involves exhaustively finding all ancestors of both nodes independently, taking their intersection, and returning the lowest common one. This is inefficient and Repeats unnecessary work compared to more optimized approaches.

Search p and q in the BST

Analyze Time and Space Complexity

Here is an analysis of the time and space complexity for the binary search tree lowest common ancestor algorithm:

Time Complexity:

Best case: O(1) - If p and q are directly connected to the root.
Average case: O(log n) - If the tree is balanced.
Worst case: O(n) - If the tree is a linked list (maximally unbalanced).

The algorithm traverses down from the root, branching left or right based on comparing p and q to the current node. In a balanced tree, the height is log(n) so we get log(n) traversal steps.

In an unbalanced tree, the height could be n and we could traverse all n nodes in the worst case.

Space complexity:

O(1) - No additional space used besides constant space for variables.

We only need to maintain the current node reference as we traverse down the tree. No supplementary data structures are used, so space is constant.

In summary, time complexity ranges from constant to linear depending on tree structure, but space used is always constant O(1) since we recur in-place without additional data structures. The algorithm is generally very space efficient.

Outline the Solution Recursive Approach Base Case Example 2: Two nodes Return root Two Subproblems Left subtree Right subtree

What should we return from the recursive function?

Some one is going to compare the parents of p and q. Is p == q ? Is p != q ?

Return values of the recursive call. Contract between the parent and child: - true/false (did you find the p or q node) - treenode instance - [true, node], [false, node]

Starting point: Compare root, p and q

Unit of Work
  - p < root.val => search for p in the left subtree
  - q < root.val => search for q in the left subtree
      if they are > root.val, we will search on the 
      right subtree

=> It is very similar to binary search tree in an array.

    if root.nil?
    return root
end

We will have atleast two nodes

if p.nil? || q.nil? return root end

root_val = root.val

if !p.nil? && p.val < root_val
    return lowest_common_ancestor(root.left, p, q)
elsif !q.nil? && q.val > root_val
    return lowest_common_ancestor(root.right, p, q)
elsif !q.nil? && q.val < root_val
    return lowest_common_ancestor(root.left, p, q)
elsif !p.nil? && p.val > root_val
    return lowest_common_ancestor(root.right, p, q)
end

return root

Lowest Common Ancestor of a Binary Tree Smallest Common Region Lowest Common Ancestor of a Binary Tree II Lowest Common Ancestor of a Binary Tree III Lowest Common Ancestor of a Binary Tree IV

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowest_common_ancestor(root, p, q)
   root_val = root.val

    p_val = p.val
    q_val = q.val

    if p_val > root_val && q_val > root_val
        return lowest_common_ancestor(root.right, p, q)
    elsif p_val < root_val && q_val < root_val
        return lowest_common_ancestor(root.left, p, q)
    end

     return root 
end