Check for Duplicate Subtrees in a Binary Tree - Visualization

Problem Statement

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.

Examples

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.

Solution

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.

Algorithm Steps

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...