NUHMAN.com

🔍 Problem Statement

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

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 = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Example 2:

go

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

🧠 Approach

Unlike a Binary Search Tree (BST) where we can take advantage of the tree's properties (left smaller, right larger), in a generic binary tree, we must traverse both left and right subtrees to find the lowest common ancestor. Here's the approach:

1. Recursive DFS:

• Traverse the tree in a depth-first search (DFS) manner.
• If we find one of the nodes p or q, we return that node (it might be the LCA).
• For each node, recursively check both its left and right subtrees.
• If both left and right subtrees return non-null values, then the current node is the LCA because one node is in the left subtree and the other node is in the right subtree.
• If only one of the subtrees returns a non-null node, return that node up the recursion chain.

1. Base Case:

• If the current node is null, return null.
• If the current node matches either p or q, return the current node.

✅ 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 binary tree
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // Base case: If root is null or root matches either p or q
    if root == nil || root == p || root == q {
        return root
    }
    
    // Recursively search for LCA in the left and right subtrees
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    
    // If both left and right are non-null, root is the LCA
    if left != nil && right != nil {
        return root
    }
    
    // Otherwise, return the non-null subtree (either left or right)
    if left != nil {
        return left
    }
    return right
}

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

    root := &TreeNode{Val: values[0]}
    nodes := []*TreeNode{root}
    i := 1
    for len(nodes) > 0 && i < len(values) {
        node := nodes[0]
        nodes = nodes[1:]

        if values[i] != -1 {
            node.Left = &TreeNode{Val: values[i]}
            nodes = append(nodes, node.Left)
        }
        i++

        if i < len(values) && values[i] != -1 {
            node.Right = &TreeNode{Val: values[i]}
            nodes = append(nodes, node.Right)
        }
        i++
    }
    return root
}

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

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

🧑‍💻 Explanation of the Code

1. lowestCommonAncestor function:

• This function recursively traverses the binary tree starting from the root.
• If we find a match for either p or q, we return that node.
• If we traverse both the left and right subtrees of a node and both return non-null values, the current node is the LCA because it is the first node that has both p and q as descendants.
• If only one of the subtrees returns a non-null value, that means both p and q are in that subtree, so we return the non-null node.

1. createBinaryTree helper function:

• This function is used to construct the binary tree from an array of values in level order.
• The -1 value represents a null node (to handle missing children in the binary tree).

📦 Example Usage

go

func main() {
    // Example 1: Input binary tree [3,5,1,6,2,0,8,null,null,7,4]
    root := createBinaryTree([]int{3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4})
    
    p := &TreeNode{Val: 5}
    q := &TreeNode{Val: 1}
    fmt.Println(lowestCommonAncestor(root, p, q).Val)  // Output: 3

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

⏱️ Time & Space Complexity

• Time Complexity: O(n)
• We must visit every node in the tree at most once, where n is the total number of nodes in the tree.
• Space Complexity: O(h)
• The space complexity is proportional to the height of the tree, due to the recursion stack. In the worst case (unbalanced tree), the height could be O(n), but in the best case (balanced tree), the height would be O(log n).

This solution efficiently finds the Lowest Common Ancestor of two nodes in a binary tree with a time complexity of O(n), where n is the number of nodes in the tree.