This program demonstrates how to find the lowest common ancestor (LCA) of two nodes in a binary tree. The LCA is defined as the lowest node in the tree that has both given nodes as descendants (where we allow a node to be a descendant of itself).

Program Explanation

The function to find the LCA uses a recursive approach, traversing the tree starting from the root. For each node, it checks if the current node is one of the target nodes. It then proceeds to check its left and right children. The LCA is determined by whether the current node or its children have paths to the target nodes.

Code Structure

1. TreeNode struct: Defines the structure of the binary tree nodes.
2. lowestCommonAncestor function: Recursively finds the LCA of two nodes in the binary tree.

Code with Documentation

package main

import (
    "fmt"
)

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

// lowestCommonAncestor finds the lowest common ancestor of two nodes p and q in the binary tree.
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 right
    }
    
    return left
}

func main() {
    // Construct a simple binary tree:
    //        3
    //       / \
    //      5   1
    //     / \ / \
    //    6  2 0  8
    //      / \
    //     7   4
    root := &TreeNode{3, 
        &TreeNode{5, &TreeNode{6, nil, nil}, &TreeNode{2, &TreeNode{7, nil, nil}, &TreeNode{4, nil, nil}}}, 
        &TreeNode{1, &TreeNode{0, nil, nil}, &TreeNode{8, nil, nil}}
    }
    
    p := root.Left      // Node 5
    q := root.Left.Right.Right  // Node 4
    
    lca := lowestCommonAncestor(root, p, q)
    fmt.Println("LCA of", p.Val, "and", q.Val, "is:", lca.Val) // Should output 5
}

Conclusion

The provided Go code allows for efficient determination of the lowest common ancestor within a binary tree using a simple recursive approach. This functionality is crucial for applications in computational biology, networking, and the implementation of hierarchical structures in databases and file systems.