Program Structure

This Go program utilizes a recursive approach combined with a map (hash table) to identify duplicate subtrees in a binary tree. The key steps include:

• Defining the structure for a binary tree node.
• Implementing a recursive function to serialize the tree structure as a string.
• Using a map to keep track of the serialized subtree strings and their occurrence count.
• Collecting the roots of duplicate subtrees for output.

Go Code

package main

import (
    "fmt"
    "strconv"
)

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

var subtreeCount map[string]int
var result []*TreeNode

// serialize serializes the subtree rooted at the given node into a string.
func serialize(node *TreeNode) string {
    if node == nil {
        return "#"
    }
    serial := strconv.Itoa(node.Val) + "," + serialize(node.Left) + "," + serialize(node.Right)
    subtreeCount[serial]++
    
    // If this serialization has occurred more than once, we add the node to the result.
    if subtreeCount[serial] == 2 {
        result = append(result, node)
    }
    return serial
}

// findDuplicateSubtrees returns all duplicate subtrees in the binary tree.
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    subtreeCount = make(map[string]int)
    result = []*TreeNode{}
    serialize(root)
    return result
}

// Helper function to print the values of the duplicate subtrees.
func printDuplicateSubtrees(duplicates []*TreeNode) {
    for _, node := range duplicates {
        fmt.Println(node.Val)
    }
}

// Main function to demonstrate the functionality.
func main() {
    // Creating a sample binary tree
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 2}
    root.Left.Right.Left = &TreeNode{Val: 4}
    root.Right.Right = &TreeNode{Val: 4}

    duplicates := findDuplicateSubtrees(root)
    fmt.Println("Duplicate Subtrees (Root Values):")
    printDuplicateSubtrees(duplicates)
}
    

Explanation

The program begins by defining the TreeNode struct to represent nodes in the binary tree. The subtreeCount map tracks how many times each serialized subtree appears, and result stores the roots of the duplicate subtrees.

The serialize function performs a post-order traversal of the tree. It generates a unique string for each subtree and updates the subtreeCount. If a subtree’s serialization is found more than once, its root is added to the result.

The findDuplicateSubtrees function initializes the necessary data structures and starts the serialization process.

Finally, the main function creates a sample binary tree, invokes the function to find duplicates, and prints the values of the duplicate subtrees.