ProgramGuru

Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More

Problem and examples

Given a binary tree, determine whether it contains any duplicate subtrees of size two or more. Two subtrees are considered duplicate if they have the same structure and the same node values. Note that subtrees of size 1 (single leaf nodes) should not be considered for duplication check.
Input Tree Has Duplicate Subtrees? Description
[1, 2, 3, 4, null, 2, 4, null, null, 4] true The subtree [4] appears more than once and so does [2, 4].
[1, 2, 3, 4, 5, 6, 7] false All subtrees are unique; no duplication occurs.
[1, 1, 1, null, null, null, 1] true The subtree consisting of just node [1] is duplicated multiple times.
[] false An empty tree has no subtrees and thus no duplicates.
[1] false A single-node tree cannot contain any duplicate subtrees.

How it works

Understanding the Problem

We are given a binary tree, and we need to determine whether it contains any duplicate subtrees of size 2 or more. This means we are looking for subtrees — not just nodes — that appear more than once in the tree and are structurally and numerically identical. A subtree must have at least two nodes to be considered in this check.

For example, consider this tree: 


      1
     /     2   3
   /   / 
  4   2
     / 
    4

Here, the subtree 2 → 4 appears twice, making it a duplicate. We must identify such cases, not just repeated values, but repeated structures with the same values.

Step-by-Step Solution with Example

Step 1: Choose a Traversal Strategy

To detect and compare subtrees effectively, we use postorder traversal (left, right, root). This allows us to serialize the entire subtree structure in a bottom-up way, ensuring both children are processed before their parent.

Step 2: Serialize Each Subtree

During traversal, we convert each subtree into a string. For example, a subtree like: 


  2
 /
4
Would serialize into 2,4,#,#,# (where # denotes a null child). This encoding captures both the structure and node values.

Step 3: Store Serialized Subtrees

We store each serialized subtree string in a hash map (dictionary). If a serialization appears more than once, it means the same subtree exists in multiple places. However, we ignore subtrees of size 1 (like just a node without children).

Step 4: Identify Duplicates

While inserting into the hash map, if we see the same serialized string again, and it represents a subtree of at least size 2, we mark that as a duplicate. As soon as we find one, we can return true (unless we are collecting all duplicates).

Step 5: Apply to Our Example

Let’s walk through the tree: 


      1
     /     2   3
   /   / 
  4   2
     / 
    4
  • Subtree rooted at left 2: 2,4,#,#,#
  • Subtree rooted at right 2: 2,4,#,#,#

The same serialization appears twice — these are duplicate subtrees of size ≥ 2. So, we return true.

Edge Cases

Case 1: Tree with Obvious Duplicate Subtrees

Subtrees that are exactly the same in structure and values appear in multiple places. These are the main targets of the algorithm.

Case 2: Tree with All Unique Subtrees

Even if node values repeat, if the subtree structures differ, it’s not a duplicate. We only consider both structure and value.

Case 3: Tree with a Single Node

A tree with only one node has no subtree of size ≥ 2. Thus, no duplicates are possible — return false.

Case 4: Empty Tree

If the tree is empty (null root), it contains no subtrees. This is a trivial case — return false.

Finally

This problem teaches an important lesson in structural comparisons, not just value matching. Using postorder traversal and serialization is an elegant way to compare subtrees efficiently. Remember to only consider subtrees of size 2 or more, and handle trivial cases early to avoid unnecessary computation. This is a great example of applying tree traversal, hashing, and string encoding together to solve a real-world structural duplication problem.

  1. Traverse the binary tree in a postorder manner and serialize each subtree into a string representation.
  2. For each node, if the node is not a leaf (i.e. it has at least one child), store its serialized string in a hash map with a frequency count.
  3. If the frequency of any serialized subtree becomes 2 (or more), mark that duplicate has been found.
  4. After processing all nodes, if a duplicate subtree (of size 2 or more) is detected, return true; otherwise, return false.

Implementation and efficiency

C implementation

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

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

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

#define MAX 1000
char* seen[MAX];
int seenCount[MAX];
int seenSize = 0;
int duplicate = 0;

char* serialize(TreeNode* node) {
    if (!node) {
        char* s = malloc(2);
        strcpy(s, "#");
        return s;
    }
    char* left = serialize(node->left);
    char* right = serialize(node->right);
    char buffer[256];
    snprintf(buffer, sizeof(buffer), "%d,%s,%s", node->val, left, right);
    char* subtree = strdup(buffer);
    if (node->left || node->right) {
        for (int i = 0; i < seenSize; i++) {
            if (strcmp(seen[i], subtree) == 0) {
                seenCount[i]++;
                if (seenCount[i] == 2) duplicate = 1;
                free(left); free(right);
                return subtree;
            }
        }
        seen[seenSize] = strdup(subtree);
        seenCount[seenSize++] = 1;
    }
    free(left); free(right);
    return subtree;
}

int hasDuplicateSubtrees(TreeNode* root) {
    seenSize = 0;
    duplicate = 0;
    char* s = serialize(root);
    free(s);
    return duplicate;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->left->left = createNode(4);
    root->right = createNode(3);
    root->right->left = createNode(2);
    root->right->left->left = createNode(4);
    root->right->right = createNode(4);
    printf("%d\n", hasDuplicateSubtrees(root));
    return 0;
}

C++ implementation

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

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

class DuplicateSubtreeChecker {
public:
    bool duplicate = false;
    unordered_map<string, int> seen;

    string serialize(TreeNode* node) {
        if (!node) return "#";
        string left = serialize(node->left);
        string right = serialize(node->right);
        string subtree = to_string(node->val) + "," + left + "," + right;
        if (node->left || node->right) {
            seen[subtree]++;
            if (seen[subtree] == 2) duplicate = true;
        }
        return subtree;
    }

    bool hasDuplicateSubtrees(TreeNode* root) {
        serialize(root);
        return duplicate;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(4);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(2);
    root->right->left->left = new TreeNode(4);
    root->right->right = new TreeNode(4);
    DuplicateSubtreeChecker checker;
    cout << checker.hasDuplicateSubtrees(root) << endl;
    return 0;
}

Python implementation

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

def hasDuplicateSubtrees(root):
    seen = {}
    duplicate = False

    def serialize(node):
        nonlocal duplicate
        if not node:
            return '#'
        left = serialize(node.left)
        right = serialize(node.right)
        subtree = f"{node.val},{left},{right}"
        if node.left or node.right:
            seen[subtree] = seen.get(subtree, 0) + 1
            if seen[subtree] == 2:
                duplicate = True
        return subtree

    serialize(root)
    return duplicate

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
    print(hasDuplicateSubtrees(root))

Java implementation

import java.util.*;

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

public class DuplicateSubtreeChecker {
    boolean duplicate = false;
    Map<String, Integer> seen = new HashMap<>();

    public String serialize(TreeNode node) {
        if (node == null) return "#";
        String left = serialize(node.left);
        String right = serialize(node.right);
        String subtree = node.val + "," + left + "," + right;
        if (node.left != null || node.right != null) {
            seen.put(subtree, seen.getOrDefault(subtree, 0) + 1);
            if (seen.get(subtree) == 2) {
                duplicate = true;
            }
        }
        return subtree;
    }

    public boolean hasDuplicateSubtrees(TreeNode root) {
        serialize(root);
        return duplicate;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(4);
        root.right.right = new TreeNode(4);
        DuplicateSubtreeChecker checker = new DuplicateSubtreeChecker();
        System.out.println(checker.hasDuplicateSubtrees(root));
    }
}

JavaScript implementation

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

function hasDuplicateSubtrees(root) {
    const seen = new Map();
    let duplicate = false;

    function serialize(node) {
        if (!node) return '#';
        const left = serialize(node.left);
        const right = serialize(node.right);
        const subtree = node.val + ',' + left + ',' + right;
        if (node.left || node.right) {
            seen.set(subtree, (seen.get(subtree) || 0) + 1);
            if (seen.get(subtree) === 2) {
                duplicate = true;
            }
        }
        return subtree;
    }

    serialize(root);
    return duplicate;
}

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(hasDuplicateSubtrees(root));

Go implementation

package main

import (
    "fmt"
    "strconv"
)

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

var seen map[string]int
var duplicate bool

func serialize(node *TreeNode) string {
    if node == nil {
        return "#"
    }
    left := serialize(node.Left)
    right := serialize(node.Right)
    subtree := strconv.Itoa(node.Val) + "," + left + "," + right
    if node.Left != nil || node.Right != nil {
        seen[subtree]++
        if seen[subtree] == 2 {
            duplicate = true
        }
    }
    return subtree
}

func hasDuplicateSubtrees(root *TreeNode) bool {
    seen = make(map[string]int)
    duplicate = false
    serialize(root)
    return duplicate
}

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}}}
    fmt.Println(hasDuplicateSubtrees(root))
}

Rust implementation

use std::collections::HashMap;

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

fn serialize(node: &Option<Box<TreeNode>>, seen: &mut HashMap<String, i32>, duplicate: &mut bool) -> String {
    if let Some(n) = node {
        let left = serialize(&n.left, seen, duplicate);
        let right = serialize(&n.right, seen, duplicate);
        let subtree = format!("{}, {}, {}", n.val, left, right);
        if n.left.is_some() || n.right.is_some() {
            let counter = seen.entry(subtree.clone()).or_insert(0);
            *counter += 1;
            if *counter == 2 {
                *duplicate = true;
            }
        }
        subtree
    } else {
        "#".to_string()
    }
}

fn has_duplicate_subtrees(root: Option<Box<TreeNode>>) -> bool {
    let mut seen = HashMap::new();
    let mut duplicate = false;
    serialize(&root, &mut seen, &mut duplicate);
    duplicate
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode {
                val: 2,
                left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
                right: None,
            })),
            right: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
        })),
    }));
    println!("{}", has_duplicate_subtrees(root));
}

Kotlin implementation

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

fun hasDuplicateSubtrees(root: TreeNode?): Boolean {
    val seen = mutableMapOf<String, Int>()
    var duplicate = false

    fun serialize(node: TreeNode?): String {
        if (node == null) return "#"
        val left = serialize(node.left)
        val right = serialize(node.right)
        val subtree = "${node.`val`},$left,$right"
        if (node.left != null || node.right != null) {
            seen[subtree] = seen.getOrDefault(subtree, 0) + 1
            if (seen[subtree] == 2) duplicate = true
        }
        return subtree
    }

    serialize(root)
    return duplicate
}

fun main() {
    val root = TreeNode(1,
        TreeNode(2, TreeNode(4)),
        TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4))
    )
    println(hasDuplicateSubtrees(root))
}

Swift implementation

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

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func hasDuplicateSubtrees(_ root: TreeNode?) -> Bool {
    var seen = [String: Int]()
    var duplicate = false

    @discardableResult
    func serialize(_ node: TreeNode?) -> String {
        guard let node = node else { return "#" }
        let left = serialize(node.left)
        let right = serialize(node.right)
        let subtree = "\(node.val),\(left),\(right)"
        if node.left != nil || node.right != nil {
            seen[subtree, default: 0] += 1
            if seen[subtree] == 2 {
                duplicate = true
            }
        }
        return subtree
    }

    serialize(root)
    return duplicate
}

let root = TreeNode(1,
    TreeNode(2, TreeNode(4)),
    TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4))
)
print(hasDuplicateSubtrees(root))

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 hasDuplicateSubtrees(root: TreeNode | null): boolean {
    const seen: Map<string, number> = new Map();
    let duplicate = false;

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

    serialize(root);
    return duplicate;
}

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(hasDuplicateSubtrees(root));