Lowest Common Ancestor in Binary Tree in DSA Go - Build from Scratch

Lowest Common Ancestor in Binary Tree

📖 Scenario: You are working on a family tree application. You want to find the closest common ancestor of two family members in the tree.

🎯 Goal: Build a program that finds the Lowest Common Ancestor (LCA) of two nodes in a binary tree.

📋 What You'll Learn

Create a binary tree with specific nodes

Add variables for the two target nodes

Implement a function to find the LCA

Print the value of the LCA node

💡 Why This Matters

🌍 Real World

Finding the lowest common ancestor is useful in family trees, organizational charts, and network routing to find shared connections.

💼 Career

Understanding tree traversal and recursive algorithms is important for software engineering roles involving data structures, databases, and system design.

1

Create the Binary Tree

Create a binary tree with the following structure using TreeNode structs:

Root node with value 3
Left child with value 5
Right child with value 1
Left child of node 5 with value 6
Right child of node 5 with value 2
Left child of node 1 with value 0
Right child of node 1 with value 8
Left child of node 2 with value 7
Right child of node 2 with value 4
Assign the root node to a variable called root.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    // Create the binary tree nodes and link them
    // Your code here
}

Hint

Start by creating the root node with value 3. Then create child nodes and assign them to the Left and Right fields accordingly.

2

Set Target Nodes for LCA

Create two variables called p and q that point to the nodes with values 5 and 1 respectively in the tree.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}
    root.Left.Right.Left = &TreeNode{Val: 7}
    root.Left.Right.Right = &TreeNode{Val: 4}

    // Create variables p and q for nodes with values 5 and 1
    // Your code here
}

Hint

Assign p to the left child of root and q to the right child of root.

3

Implement the Lowest Common Ancestor Function

Write a function called lowestCommonAncestor that takes root, p, and q as parameters (all of type *TreeNode) and returns the lowest common ancestor node. Use recursion to find the LCA.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // Implement the recursive LCA logic here
    // Your code here
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}
    root.Left.Right.Left = &TreeNode{Val: 7}
    root.Left.Right.Right = &TreeNode{Val: 4}

    p := root.Left
    q := root.Right
}

Hint

Use recursion to search left and right subtrees. If both sides return non-nil, current node is LCA. If one side returns non-nil, return that side.

4

Print the Lowest Common Ancestor Value

Call the lowestCommonAncestor function with root, p, and q. Print the Val field of the returned node using fmt.Println.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}
    root.Left.Right.Left = &TreeNode{Val: 7}
    root.Left.Right.Right = &TreeNode{Val: 4}

    p := root.Left
    q := root.Right

    // Print the LCA value
    // Your code here
}

Hint

Call lowestCommonAncestor(root, p, q) and store the result in a variable. Then print the Val of that variable.