← Back to DevBytes
Go August 06, 2026 12 min read

Solving Lowest Common Ancestor in Go: Step-by-Step Guide

Solving Lowest Common Ancestor in Go: Step-by-Step Guide

The Lowest Common Ancestor (LCA) problem is one of the most classic and frequently asked questions in technical interviews and competitive programming. Given a tree (usually a binary tree) and two nodes, the LCA is the deepest node that has both of the given nodes as descendants. In this tutorial, we will explore what LCA is, why it matters, and how to implement it efficiently in Go.

What Is the Lowest Common Ancestor?

In a tree data structure, the Lowest Common Ancestor of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants. A node can also be considered a descendant of itself, which is an important detail when one of the input nodes is an ancestor of the other.

For example, consider the following binary tree:

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

If we want to find the LCA of nodes 5 and 1, the answer is 3 because it is the lowest node that contains both. If we want the LCA of nodes 5 and 4, the answer is 5 itself, since 4 is a descendant of 5 and a node is its own descendant.

Why the LCA Problem Matters

The LCA problem is not just an academic exercise. It has real-world applications across many domains:

Understanding how to solve LCA efficiently gives you a strong foundation in tree traversal, recursion, and algorithmic thinking.

Defining the Tree Structure in Go

Before we can solve the problem, we need to define a binary tree node. In Go, this is typically done using a struct with pointers to left and right children.

package main

import "fmt"

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

This simple struct gives us everything we need: a value to identify the node and two pointers to its children. For more complex scenarios, you might add a parent pointer, which we will discuss later.

Solution 1: Recursive Depth-First Search

The most intuitive approach to solving LCA is to use recursion. The idea is to traverse the tree from the root and return a node when we find either p or q. If both the left and right subtrees return a non-nil node, it means the current node is the LCA. If only one subtree returns a non-nil node, we propagate that node upward.

Here is the complete implementation:

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // Base case: if root is nil, or root is one of p or q, return root.
    if root == nil || root == p || root == q {
        return root
    }

    // Recurse on the left and right subtrees.
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // If both sides returned a non-nil node, root is the LCA.
    if left != nil && right != nil {
        return root
    }

    // Otherwise, return whichever side found a node.
    if left != nil {
        return left
    }
    return right
}

Let us break down how this works step by step:

The time complexity of this solution is O(n) where n is the number of nodes, because in the worst case we visit every node. The space complexity is O(h) where h is the height of the tree, due to the recursion stack.

Testing the Recursive Solution

To verify our solution works correctly, let us build the example tree and run a few test cases.

func main() {
    // Build the tree:
    //        3
    //       / \
    //      5   1
    //     / \ / \
    //    6  2 0  8
    //      / \
    //     7   4
    root := &TreeNode{Val: 3}
    node5 := &TreeNode{Val: 5}
    node1 := &TreeNode{Val: 1}
    node6 := &TreeNode{Val: 6}
    node2 := &TreeNode{Val: 2}
    node0 := &TreeNode{Val: 0}
    node8 := &TreeNode{Val: 8}
    node7 := &TreeNode{Val: 7}
    node4 := &TreeNode{Val: 4}

    root.Left = node5
    root.Right = node1
    node5.Left = node6
    node5.Right = node2
    node1.Left = node0
    node1.Right = node8
    node2.Left = node7
    node2.Right = node4

    // Test 1: LCA of 5 and 1 should be 3
    lca := lowestCommonAncestor(root, node5, node1)
    fmt.Printf("LCA of 5 and 1: %d\n", lca.Val)

    // Test 2: LCA of 5 and 4 should be 5
    lca = lowestCommonAncestor(root, node5, node4)
    fmt.Printf("LCA of 5 and 4: %d\n", lca.Val)

    // Test 3: LCA of 6 and 4 should be 5
    lca = lowestCommonAncestor(root, node6, node4)
    fmt.Printf("LCA of 6 and 4: %d\n", lca.Val)

    // Test 4: LCA of 7 and 8 should be 3
    lca = lowestCommonAncestor(root, node7, node8)
    fmt.Printf("LCA of 7 and 8: %d\n", lca.Val)
}

When you run this program, the output should be:

LCA of 5 and 1: 3
LCA of 5 and 4: 5
LCA of 6 and 4: 5
LCA of 7 and 8: 3

Solution 2: Using Parent Pointers

Sometimes the tree nodes include a pointer to their parent. When this is available, we can solve the LCA problem without recursion by finding the intersection of the two paths from p and q up to the root. This approach is similar to finding the intersection point of two linked lists.

First, let us update our node definition to include a parent pointer:

type TreeNodeWithParent struct {
    Val    int
    Left   *TreeNodeWithParent
    Right  *TreeNodeWithParent
    Parent *TreeNodeWithParent
}

Now we can implement the LCA using the two-pointer technique:

func lowestCommonAncestorWithParent(p, q *TreeNodeWithParent) *TreeNodeWithParent {
    // Collect the path from p to root.
    pathP := []*TreeNodeWithParent{}
    for curr := p; curr != nil; curr = curr.Parent {
        pathP = append(pathP, curr)
    }

    // Collect the path from q to root.
    pathQ := []*TreeNodeWithParent{}
    for curr := q; curr != nil; curr = curr.Parent {
        pathQ = append(pathQ, curr)
    }

    // Reverse both paths so they go from root to the node.
    reverse := func(path []*TreeNodeWithParent) {
        for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
            path[i], path[j] = path[j], path[i]
        }
    }
    reverse(pathP)
    reverse(pathQ)

    // Find the last common node in both paths.
    var lca *TreeNodeWithParent
    for i := 0; i < len(pathP) && i < len(pathQ); i++ {
        if pathP[i] == pathQ[i] {
            lca = pathP[i]
        } else {
            break
        }
    }
    return lca
}

This approach has a time complexity of O(h) and a space complexity of O(h) for storing the paths. An alternative that uses O(1) space involves advancing two pointers and swapping them when they reach the root, similar to the intersection of two linked lists.

Solution 3: Binary Search Tree Optimization

If the tree is a Binary Search Tree (BST), we can solve the LCA problem more efficiently by leveraging the BST property: for any node, all values in the left subtree are smaller and all values in the right subtree are larger. This allows us to navigate directly toward the LCA without exploring the entire tree.

func lowestCommonAncestorBST(root, p, q *TreeNode) *TreeNode {
    curr := root
    for curr != nil {
        if p.Val < curr.Val && q.Val < curr.Val {
            // Both nodes are in the left subtree.
            curr = curr.Left
        } else if p.Val > curr.Val && q.Val > curr.Val {
            // Both nodes are in the right subtree.
            curr = curr.Right
        } else {
            // The nodes diverge here, or one is the ancestor of the other.
            return curr
        }
    }
    return nil
}

This iterative solution runs in O(h) time and uses O(1) space, making it significantly more efficient than the general recursive approach when the tree is a BST.

Solution 4: Handling Multiple Queries with Preprocessing

If you need to answer many LCA queries on the same tree, a naive recursive approach for each query becomes expensive. In that case, you can preprocess the tree using techniques like binary lifting, which allows each query to be answered in O(log n) time after O(n log n) preprocessing.

Here is a simplified version of binary lifting in Go:

type LCAPreprocessor struct {
    depth  []int
    parent [][]int // parent[k][v] is the 2^k-th ancestor of v
    log    int
    nodes  []*TreeNode
    index  map[*TreeNode]int
}

func NewLCAPreprocessor(root *TreeNode) *LCAPreprocessor {
    nodes := []*TreeNode{}
    index := make(map[*TreeNode]int)

    // Flatten the tree and assign indices.
    var flatten func(node, par *TreeNode, depth int)
    flatten = func(node, par *TreeNode, depth int) {
        if node == nil {
            return
        }
        idx := len(nodes)
        index[node] = idx
        nodes = append(nodes, node)
        _ = depth
        flatten(node.Left, node, depth+1)
        flatten(node.Right, node, depth+1)
    }
    flatten(root, nil, 0)

    n := len(nodes)
    log := 0
    for (1 << log) <= n {
        log++
    }

    depth := make([]int, n)
    parent := make([][]int, log)
    for k := range parent {
        parent[k] = make([]int, n)
        for i := range parent[k] {
            parent[k][i] = -1
        }
    }

    // BFS to compute depth and immediate parents.
    type entry struct {
        node *TreeNode
        par  int
        dep  int
    }
    queue := []entry{{root, -1, 0}}
    visited := make(map[*TreeNode]bool)
    for len(queue) > 0 {
        e := queue[0]
        queue = queue[1:]
        if visited[e.node] {
            continue
        }
        visited[e.node] = true
        idx := index[e.node]
        depth[idx] = e.dep
        parent[0][idx] = e.par
        if e.node.Left != nil {
            queue = append(queue, entry{e.node.Left, idx, e.dep + 1})
        }
        if e.node.Right != nil {
            queue = append(queue, entry{e.node.Right, idx, e.dep + 1})
        }
    }

    // Fill the binary lifting table.
    for k := 1; k < log; k++ {
        for v := 0; v < n; v++ {
            if parent[k-1][v] != -1 {
                parent[k][v] = parent[k-1][parent[k-1][v]]
            }
        }
    }

    return &LCAPreprocessor{
        depth:  depth,
        parent: parent,
        log:    log,
        nodes:  nodes,
        index:  index,
    }
}

func (lca *LCAPreprocessor) Query(p, q *TreeNode) *TreeNode {
    u := lca.index[p]
    v := lca.index[q]

    // Ensure u is the deeper node.
    if lca.depth[u] < lca.depth[v] {
        u, v = v, u
    }

    // Lift u to the same depth as v.
    diff := lca.depth[u] - lca.depth[v]
    for k := 0; k < lca.log; k++ {
        if (diff>>k)&1 == 1 {
            u = lca.parent[k][u]
        }
    }

    if u == v {
        return lca.nodes[u]
    }

    // Lift both nodes together until their parents match.
    for k := lca.log - 1; k >= 0; k-- {
        if lca.parent[k][u] != lca.parent[k][v] {
            u = lca.parent[k][u]
            v = lca.parent[k][v]
        }
    }

    return lca.nodes[lca.parent[0][u]]
}

This is more complex, but it pays off when you have hundreds or thousands of LCA queries on a large static tree. The preprocessing cost is amortized across all queries.

Best Practices

When implementing LCA solutions in Go, keep the following best practices in mind:

Common Pitfalls to Avoid

Even experienced developers make mistakes when implementing LCA. Here are some common pitfalls:

Conclusion

The Lowest Common Ancestor problem is a fundamental algorithm that every Go developer should understand. We started with the recursive DFS approach, which is elegant and works for any binary tree, then explored parent-pointer-based solutions, BST-specific optimizations, and binary lifting for handling multiple queries efficiently. Each approach has its own trade-offs in terms of time complexity, space complexity, and implementation complexity. By choosing the right technique for your specific use case and following best practices around input validation, pointer comparison, and testing, you can implement robust LCA solutions that perform well in production systems. Whether you are building a version control tool, a routing algorithm, or simply preparing for a coding interview, mastering LCA in Go will serve you well.

— Ad —

Google AdSense will appear here after approval

← Back to all articles