235.lowest-common-acestor-of-a-binary-search-tree.md

235. Lowest Common Ancestor of a Binary Search Tree

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
        50
      /    \
    20      70
   /  \    /  \
  10  30  60  80
p = 10,
q = 30
Output: 20 

Input:
        50
      /    \
    20      70
   /  \    /  \
  10  30  60  80
p = 20,
q = 30
Output: 20 

Edge / Corner Cases

• The p and q is the same.

Input: Any
Output: `p` or `q`.

Iterative Once

We iterate from root, and like normal way in BST search:

• If the current value < p, q, that means the two nodes are both in right subtree, so we go right child.

node       
   \       
    p, q 

• If p, q < the current value, that means the two nodes are both in left subtree, so we go left child.

     node
    /    
  p, q 

• If we find a node such that p < node.value < q or reversed order, then p and q must be in different child, so the current node is lowest common ancestor.

     node        node
    /    \      /    \
   p      q    q      p

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || p == null || q == null) return null
    var node: TreeNode? = root
    while (node != null) {
        if (node.`val` > p.`val` && node.`val` > q.`val`) node = node.left
        else if (node.`val` < p.`val` && node.`val` < q.`val`) node = node.right
        else break
    }
    return node
}

• Time Complexity: O(h), the worst case is O(n).
• Space Complexity: O(1).

Recursive

The same idea as iterative once solution.

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || p == null || q == null) return null
    if (root.`val` < p.`val` && root.`val` < q.`val`) return lowestCommonAncestor(root.right, p, q)
    if (root.`val` > p.`val` && root.`val` > q.`val`) return lowestCommonAncestor(root.left, p, q)
    else return root
}

• Time Complexity: O(h).
• Space Complexity: O(h).

Iterative Twice

We can find the path between root to p and to q, then compare the two paths to find the lowest common ancestor.

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || p == null || q == null) return null
    val pathP = getPath(root, p)
    val pathQ = getPath(root, q)
    
    var i = 0
    var result: TreeNode? = null
    while (i < pathP.size && i < pathQ.size) {
        if (pathP[i] == pathQ[i]) result = pathP[i]
        else break
        i++
    }
    return result
}

private fun getPath(root: TreeNode, target: TreeNode): List<TreeNode> {
    val path = mutableListOf<TreeNode>()
    var node: TreeNode? = root
    while (node != null) {
        path.add(node)
        if (node == target) break
        if (target.`val` > node.`val`) node = node.right
        else node = node.left
    }
    return path
}

• Time Complexity: O(n).
• Space Complexity: O(n).