NUHMAN.com

🔍 Problem Statement

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

According to the definition of a binary search tree:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.

The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example 1:

go

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Example 2:

go

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2

🧠 Approach

Since the tree is a binary search tree (BST), we can use its properties to efficiently find the lowest common ancestor (LCA) of two nodes:

1. Step 1: Traverse the tree:

• Start from the root node and compare the values of p and q with the current node's value.

1. Step 2: Check the relations between nodes:

• If both p and q are smaller than the current node’s value, the LCA must lie in the left subtree.
• If both p and q are greater than the current node’s value, the LCA must lie in the right subtree.
• If one of p and q is smaller and the other is larger (or one of them is equal to the current node), then the current node is the LCA.

✅ Go Implementation

go

package main

import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Function to find the lowest common ancestor of a BST
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // Start from the root node
    current := root
    
    // Traverse the tree
    for current != nil {
        if p.Val < current.Val && q.Val < current.Val {
            // Both p and q are smaller than current node, go to left subtree
            current = current.Left
        } else if p.Val > current.Val && q.Val > current.Val {
            // Both p and q are greater than current node, go to right subtree
            current = current.Right
        } else {
            // One of p or q is equal to current node or they are on different sides
            return current
        }
    }
    
    return nil
}

// Helper function to create a binary tree from an array of values (level order)
func createBST(values []int) *TreeNode {
    if len(values) == 0 {
        return nil
    }

    root := &TreeNode{Val: values[0]}
    for i := 1; i < len(values); i++ {
        insertIntoBST(root, values[i])
    }
    return root
}

// Helper function to insert a value into a BST
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    } else {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

// Test the lowestCommonAncestor function
func main() {
    // Example 1: Input BST [6,2,8,0,4,7,9,null,null,3,5]
    bst := createBST([]int{6, 2, 8, 0, 4, 7, 9, 3, 5})
    
    p := &TreeNode{Val: 2}
    q := &TreeNode{Val: 8}
    fmt.Println(lowestCommonAncestor(bst, p, q).Val)  // Output: 6

    p = &TreeNode{Val: 2}
    q = &TreeNode{Val: 4}
    fmt.Println(lowestCommonAncestor(bst, p, q).Val)  // Output: 2
}

🧑‍💻 Explanation of the Code

1. lowestCommonAncestor function:

• We start at the root node and iterate through the tree.
• If both p and q have values smaller than the current node, we move to the left subtree.
• If both p and q have values greater than the current node, we move to the right subtree.
• If one of p and q is smaller and the other is greater (or one of them is equal to the current node), then the current node is the LCA.

1. createBST and insertIntoBST helper functions:

• These helper functions are used to create a binary search tree from a list of values and insert new values into the tree while maintaining the BST properties.

📦 Example Usage

go

func main() {
    // Example 1: Input BST [6,2,8,0,4,7,9,null,null,3,5]
    bst := createBST([]int{6, 2, 8, 0, 4, 7, 9, 3, 5})
    
    p := &TreeNode{Val: 2}
    q := &TreeNode{Val: 8}
    fmt.Println(lowestCommonAncestor(bst, p, q).Val)  // Output: 6

    p = &TreeNode{Val: 2}
    q = &TreeNode{Val: 4}
    fmt.Println(lowestCommonAncestor(bst, p, q).Val)  // Output: 2
}

⏱️ Time & Space Complexity

• Time Complexity: O(h)
• Where h is the height of the binary search tree. In the worst case (unbalanced tree), the height can be O(n), but for a balanced BST, the height is O(log n).
• Space Complexity: O(1)
• We only use a constant amount of extra space for pointers (current, p, and q).

This solution efficiently finds the Lowest Common Ancestor of two nodes in a Binary Search Tree in O(h) time, where h is the height of the tree.