Check for Duplicate Subtrees in a Binary Tree - Visualization
Problem Statement
Examples
Solution
Algorithm Steps
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
Loading comments...