Problem Statement:
You are given a binary tree, you need to find all the duplicate sub trees.
Example
Input : 1 / \ 2 3 / / \ 4 2 4 / 4 Output : 2 / and 4 4
Solution
The solution is very simple, we need to take use of hashing and in-order traversal.
We first do an inorder traversal and store it in a hash table.
Then check if a string value is already present in the map i.e map[string] is equal to one print the value of the node.
Else increment value in the map by 1
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <queue> #include <vector> #include <stack> #include <unordered_map> using namespace std; struct node { int data; node *left; node *right; node(int data) { this->data = data; this->left = this->right = nullptr; } }; string inorder(node* node, unordered_map<string, int>& m) { if (!node) return ""; string str = "("; str += inorder(node->left, m); str += to_string(node->data); str += inorder(node->right, m); str += ")"; if (m[str] == 1) cout << node->data << " "; m[str]++; return str; } void print_dups(node* root) { unordered_map<string, int> m; inorder(root, m); } int main() { node* root = NULL; root = new node(1); root->left = new node(2); root->right = new node(3); root->left->left = new node(4); root->right->left = new node(2); root->right->left->left = new node(4); root->right->right = new node(4); print_dups(root); return 0; }
Output:
4 2