# Subtree query (suboptimal)

• Subtree query algorithm. Not the fastest or cleanest solution, but it works.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
struct TreeTraversalNode{
TreeNode* node;
int subtree_size_left;
int subtree_size_right;
int subtree_size;
int node_value;
bool is_duplicate;
//TreeTraversalNode();
};

class Solution {
public:
void traverseTree(TreeNode* node, vector<TreeTraversalNode>& traversal_nodes) {
if (!node)
return;

TreeTraversalNode traversal_node;
traversal_node.node = node;
traversal_node.subtree_size = 1;
traversal_node.subtree_size_left = 0;
traversal_node.subtree_size_right = 0;
traversal_node.node_value = node->val;
traversal_node.is_duplicate = false;

int node_id = traversal_nodes.size();

traversal_nodes.push_back(traversal_node);

if (node->left) {
traverseTree(node->left, traversal_nodes);
traversal_nodes[node_id].subtree_size_left = traversal_nodes[node_id + 1].subtree_size;
traversal_nodes[node_id].subtree_size += traversal_nodes[node_id].subtree_size_left;
}

int node_id_right = traversal_nodes.size();

if (node->right) {
traverseTree(node->right, traversal_nodes);
traversal_nodes[node_id].subtree_size_right = traversal_nodes[node_id_right].subtree_size;
traversal_nodes[node_id].subtree_size += traversal_nodes[node_id].subtree_size_right;
}
}

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
vector<TreeNode*> duplicate_nodes;
vector<TreeTraversalNode> traversal_nodes;

traverseTree(root, traversal_nodes);

for (int i = 0; i < traversal_nodes.size(); i++) {
if (traversal_nodes[i].is_duplicate)
continue;

bool first_duplicate_found = false;
for (int j = i + 1; j < traversal_nodes.size(); j++) {
if (traversal_nodes[i].subtree_size_left == traversal_nodes[j].subtree_size_left &&
traversal_nodes[i].subtree_size_right == traversal_nodes[j].subtree_size_right) {
bool is_duplicate = true;
for (int k = 0; k < traversal_nodes[i].subtree_size; k++) {
if (traversal_nodes[i + k].node_value != traversal_nodes[j + k].node_value ||
(traversal_nodes[i + k].subtree_size_left != traversal_nodes[j + k].subtree_size_left &&
traversal_nodes[i + k].subtree_size_right != traversal_nodes[j + k].subtree_size_right)) {
is_duplicate = false;
break;
}
}
if (is_duplicate) {
traversal_nodes[i].is_duplicate = true;
traversal_nodes[j].is_duplicate = true;
if (!first_duplicate_found) {
duplicate_nodes.push_back(traversal_nodes[i].node);
first_duplicate_found = true;
}
}
}
}
}

return duplicate_nodes;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.