ProgramGuru

Find All Duplicate Subtrees in a Binary Tree

Problem and examples

Given the root of a binary tree, return all duplicate subtrees. For two trees to be considered duplicate, they must have the same structure and the same node values. You can return the root node of any one of the duplicate subtrees. Each duplicate subtree should be included only once in the result.
Input Tree Duplicate Subtrees (Serialized) Description
[1, 2, 3, 4, null, 2, 4, null, null, 4] ['4', '2,4,null,null,null'] The subtree rooted at value 4 appears three times. The subtree [2, 4] also appears twice.
[1, 2, 3, 4, null, 4, null, null, null, 4] ['4'] The leaf node with value 4 appears multiple times, forming duplicate subtrees.
[1, 2, 3] [] All subtrees are unique; no duplicate subtree structure exists.
[0, 0, 0, 0, null, null, 0] ['0'] The leaf node with value 0 appears three times. These are duplicate subtrees.
[2, 1, 1, null, null, null, 1] ['1'] There are multiple leaf nodes with value 1, which are considered duplicate subtrees.

How it works

Understanding the Problem

We are given a binary tree, and our goal is to find all duplicate subtrees. A duplicate subtree is one where both the structure and node values are identical to another subtree in the tree. Each duplicate should be returned only once, represented by its root node.

To identify duplicates, we must compare every subtree with all others. But doing this naively would be inefficient. Instead, we use a serialization strategy to transform each subtree into a string format, allowing quick lookup and comparison using a hash map.

Step-by-Step Solution with Example

Step 1: Visualize the Example

Let’s take the input tree: [1,2,3,4,null,2,4,null,null,4]

This corresponds to the following structure:

        1
       /       2   3
     /   /     4   2   4
       /
      4

We can observe:

  • Three nodes with value 4, all as leaf nodes.
  • Two subtrees with structure 2 → 4.
These are candidates for duplicate subtrees.

Step 2: Define Serialization Format

We perform a post-order traversal (left → right → node) and serialize each subtree into a string.

For example:

  • Leaf node 4 becomes "4,#,#"
  • Subtree 2 → 4 becomes "2,4,#,#,#"
This unique string helps us identify duplicates using a hash map that stores counts.

Step 3: Track and Detect Duplicates

We maintain a hash map where keys are serialization strings and values are their frequency.

As we serialize each subtree:

  • If a serialization is seen once, we add the subtree root to the result.
  • If it’s already seen more than once, we skip it to avoid duplicates in the result.

Step 4: Return the Result

From our example:

  • Serialization "4,#,#" appears 3 times → add one root node of 4
  • Serialization "2,4,#,#,#" appears 2 times → add one root node of 2
The final result contains the roots of these duplicate subtrees.

Edge Cases

Case 1: All Subtrees Are Unique

Input: [1,2,3]
Structure: 

  1
 / 2   3
Each node is unique. Serialized strings for each subtree do not match. Result: [].

Case 2: Empty Tree

Input: []
There are no nodes in the tree. Hence, no subtrees exist. Result: [].

Case 3: Large Tree with Many Duplicates

Ensure that your solution uses efficient traversal and hashing to handle such cases within time limits.

Finally

This problem is a great example of using serialization to simplify complex structure comparisons. It teaches you how to:

  • Break down trees into reusable string representations
  • Use hash maps to count and identify duplicates efficiently
  • Handle edge cases like null roots and small trees gracefully
This technique is widely applicable in tree-related problems where comparison is required.

  1. Perform a postorder traversal of the binary tree.
  2. For each node, generate a unique serialization string representing the subtree rooted at that node. Use a format like node.val,left_serial,right_serial.
  3. Use a hash map (or dictionary) to count the occurrences of each serialized subtree.
  4. If a serialization appears more than once, add the subtree's root to the result list (ensuring each duplicate is added only once).
  5. Return the list of duplicate subtree roots.

Implementation and efficiency

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> list:
        count = {}
        result = []
        
        def traverse(node):
            if not node:
                return '#'
            serial = f'{node.val},' + traverse(node.left) + ',' + traverse(node.right)
            count[serial] = count.get(serial, 0) + 1
            if count[serial] == 2:
                result.append(node)
            return serial
        
        traverse(root)
        return result

# Example usage:
if __name__ == '__main__':
    # Construct binary tree sample
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   2   4
    #        /
    #       4
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
    sol = Solution()
    duplicates = sol.findDuplicateSubtrees(root)
    for node in duplicates:
        print(node.val)

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    Map<String, Integer> count = new HashMap<>();
    List<TreeNode> result = new ArrayList<>();
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serialize(root);
        return result;
    }
    
    private String serialize(TreeNode node) {
        if (node == null) return "#";
        String serial = node.val + "," + serialize(node.left) + "," + serialize(node.right);
        count.put(serial, count.getOrDefault(serial, 0) + 1);
        if (count.get(serial) == 2) result.add(node);
        return serial;
    }
    
    public static void main(String[] args) {
        // Construct sample tree similar to the Python example
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(4);
        root.right.right = new TreeNode(4);
        
        Solution sol = new Solution();
        List<TreeNode> duplicates = sol.findDuplicateSubtrees(root);
        for (TreeNode node : duplicates) {
            System.out.println(node.val);
        }
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findDuplicateSubtrees(root) {
    const count = new Map();
    const result = [];
    
    function serialize(node) {
        if (!node) return '#';
        const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
        count.set(serial, (count.get(serial) || 0) + 1);
        if (count.get(serial) === 2) result.push(node);
        return serial;
    }
    
    serialize(root);
    return result;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(2, new TreeNode(4)), new TreeNode(4))
);
console.log(findDuplicateSubtrees(root));

C implementation

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Note: Implementing a full hash map in C is complex. The following is a simplified pseudo-implementation
// for educational purposes and may not handle all edge cases or memory management.

#define TABLE_SIZE 1000

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// A simple structure for hash map entries
typedef struct {
    char *key;
    int count;
    TreeNode *node; // store the first duplicate occurrence
} HashEntry;

HashEntry *hashTable[TABLE_SIZE];

unsigned int hash(const char *str) {
    unsigned int hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash % TABLE_SIZE;
}

char* serialize(TreeNode *node) {
    if (!node) return strdup("#");
    char leftSerial[256], rightSerial[256];
    char *left = serialize(node->left);
    char *right = serialize(node->right);
    snprintf(leftSerial, sizeof(leftSerial), "%s", left);
    snprintf(rightSerial, sizeof(rightSerial), "%s", right);
    free(left);
    free(right);
    char *serial = malloc(256);
    snprintf(serial, 256, "%d,%s,%s", node->val, leftSerial, rightSerial);
    return serial;
}

// Global result array (for simplicity, fixed size)
TreeNode **result;
int resultCount = 0;

void addToHash(const char *serial, TreeNode *node) {
    unsigned int index = hash(serial);
    // linear probing for simplicity
    while (hashTable[index] != NULL) {
        if (strcmp(hashTable[index]->key, serial) == 0) {
            hashTable[index]->count++;
            if (hashTable[index]->count == 2) {
                result[resultCount++] = node;
            }
            return;
        }
        index = (index + 1) % TABLE_SIZE;
    }
    HashEntry *entry = malloc(sizeof(HashEntry));
    entry->key = strdup(serial);
    entry->count = 1;
    entry->node = node;
    hashTable[index] = entry;
}

char* traverse(TreeNode *node) {
    if (!node) return strdup("#");
    char *leftSerial = traverse(node->left);
    char *rightSerial = traverse(node->right);
    char *serial = malloc(256);
    snprintf(serial, 256, "%d,%s,%s", node->val, leftSerial, rightSerial);
    addToHash(serial, node);
    free(leftSerial);
    free(rightSerial);
    return serial;
}

// Example usage:
int main() {
    // Construct tree:
    //         1
    //        / \
    //       2   3
    //      /   / \
    //     4   2   4
    //        /
    //       4
    TreeNode n4a = {4, NULL, NULL};
    TreeNode n2a = {2, &n4a, NULL};
    TreeNode n4b = {4, NULL, NULL};
    TreeNode n2b = {2, &n4b, NULL};
    TreeNode n4c = {4, NULL, NULL};
    TreeNode n3 = {3, &n2b, &n4c};
    TreeNode root = {1, &n2a, &n3};

    result = malloc(100 * sizeof(TreeNode*));
    traverse(&root);

    printf("Duplicate subtree roots (by value):\n");
    for (int i = 0; i < resultCount; i++) {
        printf("%d\n", result[i]->val);
    }

    // Free resources omitted for brevity
    return 0;
}

C++ implementation

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    unordered_map<string, int> count;
    vector<TreeNode*> result;
    
    string serialize(TreeNode* node) {
        if (!node) return "#";
        string serial = to_string(node->val) + "," + serialize(node->left) + "," + serialize(node->right);
        count[serial]++;
        if (count[serial] == 2) result.push_back(node);
        return serial;
    }
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        serialize(root);
        return result;
    }
};

int main() {
    // Construct sample tree
    TreeNode* n4a = new TreeNode(4);
    TreeNode* n2a = new TreeNode(2);
    n2a->left = n4a;
    TreeNode* n4b = new TreeNode(4);
    TreeNode* n2b = new TreeNode(2);
    n2b->left = n4b;
    TreeNode* n4c = new TreeNode(4);
    TreeNode* n3 = new TreeNode(3);
    n3->left = n2b;
    n3->right = n4c;
    TreeNode* root = new TreeNode(1);
    root->left = n2a;
    root->right = n3;
    
    Solution sol;
    vector<TreeNode*> duplicates = sol.findDuplicateSubtrees(root);
    for (auto node : duplicates) {
        cout << node->val << "\n";
    }
    return 0;
}

Go implementation

package main

import (
    "fmt"
    "strconv"
)

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

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    count := make(map[string]int)
    var result []*TreeNode

    var serialize func(*TreeNode) string
    serialize = func(node *TreeNode) string {
        if node == nil {
            return "#"
        }
        serial := strconv.Itoa(node.Val) + "," + serialize(node.Left) + "," + serialize(node.Right)
        count[serial]++
        if count[serial] == 2 {
            result = append(result, node)
        }
        return serial
    }

    serialize(root)
    return result
}

func main() {
    root := &TreeNode{1,
        &TreeNode{2, &TreeNode{4, nil, nil}, nil},
        &TreeNode{3, &TreeNode{2, &TreeNode{4, nil, nil}, nil}, &TreeNode{4, nil, nil}},
    }
    duplicates := findDuplicateSubtrees(root)
    fmt.Println("Duplicate subtree roots (by value):")
    for _, node := range duplicates {
        fmt.Println(node.Val)
    }
}

Rust implementation

use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn find_duplicate_subtrees(root: Option<&Box<TreeNode>>) -> Vec<i32> {
    let mut count = HashMap::new();
    let mut result = vec![];

    fn serialize(node: Option<&Box<TreeNode>>, count: &mut HashMap<String, usize>, result: &mut Vec<i32>) -> String {
        if let Some(n) = node {
            let serial = format!("{}, {}, {}", n.val,
                serialize(n.left.as_ref(), count, result),
                serialize(n.right.as_ref(), count, result));
            let entry = count.entry(serial.clone()).or_insert(0);
            *entry += 1;
            if *entry == 2 {
                result.push(n.val);
            }
            serial
        } else {
            "#".to_string()
        }
    }

    serialize(root, &mut count, &mut result);
    result
}

fn main() {
    let tree = Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode::new(4))),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode {
                val: 2,
                left: Some(Box::new(TreeNode::new(4))),
                right: None,
            })),
            right: Some(Box::new(TreeNode::new(4))),
        })),
    });

    let duplicates = find_duplicate_subtrees(Some(&tree));
    println!("Duplicate subtree roots (by value): {:?}", duplicates);
}

Kotlin implementation

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private val count = mutableMapOf<String, Int>()
    private val result = mutableListOf<TreeNode>()

    fun findDuplicateSubtrees(root: TreeNode?): List<TreeNode> {
        serialize(root)
        return result
    }

    private fun serialize(node: TreeNode?): String {
        if (node == null) return "#"
        val serial = "${node.`val`}," + serialize(node.left) + "," + serialize(node.right)
        count[serial] = count.getOrDefault(serial, 0) + 1
        if (count[serial] == 2) result.add(node)
        return serial
    }
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2).apply { left = TreeNode(4) }
    root.right = TreeNode(3).apply {
        left = TreeNode(2).apply { left = TreeNode(4) }
        right = TreeNode(4)
    }
    val sol = Solution()
    val duplicates = sol.findDuplicateSubtrees(root)
    println("Duplicate subtree roots (by value):")
    duplicates.forEach { println(it.`val`) }
}

Swift implementation

import Foundation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
    }
}

class Solution {
    var count = [String: Int]()
    var result = [TreeNode]()

    func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode] {
        _ = serialize(root)
        return result
    }

    func serialize(_ node: TreeNode?) -> String {
        guard let node = node else { return "#" }
        let serial = "\(node.val),\(serialize(node.left)),\(serialize(node.right))"
        count[serial, default: 0] += 1
        if count[serial] == 2 {
            result.append(node)
        }
        return serial
    }
}

// Example usage
let root = TreeNode(1)
root.left = TreeNode(2)
root.left?.left = TreeNode(4)
root.right = TreeNode(3)
root.right?.left = TreeNode(2)
root.right?.left?.left = TreeNode(4)
root.right?.right = TreeNode(4)

let solution = Solution()
let duplicates = solution.findDuplicateSubtrees(root)
print("Duplicate subtree roots (by value):")
for node in duplicates {
    print(node.val)
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findDuplicateSubtrees(root: TreeNode | null): TreeNode[] {
    const count = new Map<string, number>();
    const result: TreeNode[] = [];

    function serialize(node: TreeNode | null): string {
        if (!node) return '#';
        const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
        count.set(serial, (count.get(serial) || 0) + 1);
        if (count.get(serial) === 2) {
            result.push(node);
        }
        return serial;
    }

    serialize(root);
    return result;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(2, new TreeNode(4)), new TreeNode(4))
);
const duplicates = findDuplicateSubtrees(root);
console.log("Duplicate subtree roots (by value):");
duplicates.forEach(node => console.log(node.val));