# 12. Duplicate subtree in Binary Tree

The problem can be found at the following link: [Question Link](https://practice.geeksforgeeks.org/problems/duplicate-subtree-in-binary-tree/1)

![](https://badgen.net/badge/Level/Medium/yellow)

## My Approach

To check if a binary tree contains a duplicate subtree of size 2 or more. It does so by checking if there are any identical subtrees within the tree.

Here are the steps in my approach:

* The dupSub function does a level-order traversal of the binary tree using a queue to extract all the nodes.
* While traversing the tree, it identifies non-leaf nodes and stores them in the nodes vector.
* After collecting non-leaf nodes, it iterates through the nodes vector and compares each pair of nodes using the same function to check if they have the same structure and values. If a match is found, it returns true, indicating the presence of a duplicate subtree.
* If no duplicate subtree is found during the iteration, it returns false.

## Time and Auxiliary Space Complexity

* **Time Complexity**: The time complexity of this approach is `O(N)`, where `N` is the number of nodes in the binary tree. This is because we visit each node once to calculate its height and check the balance condition.
* **Space Complexity**: The space complexity is `O(H)`, where `H` is the height of the binary tree. In the worst case, the space complexity is `O(N + H)` for a skewed tree, and in the best case, it is `O(N)` for a balanced tree. This space is used for the recursive call stack.

## Code (C++)

```cpp
bool same(Node * x, Node * y)
{
    if((x == nullptr) ^ (y == nullptr))
        return 0;
    if((x == nullptr) and (y == nullptr))
        return 1;
    if(x -> data != y -> data)
        return 0;

    return same(x -> left, y -> left) and same(x -> right, y -> right);
}

class Solution {
  public:
    /*This function returns true if the tree contains 
    a duplicate subtree of size 2 or more else returns false*/
    int dupSub(Node *root)
    {
        vector<Node *> nodes;

        queue<Node *> q;
        q.push(root);

        while(!q.empty()){
            Node * cur = q.front();
            q.pop();

            bool leaf = 1;

            if(cur -> left != nullptr)
            {
                q.push(cur -> left);
                leaf = 0;
            }
            if(cur -> right != nullptr)
            {
                q.push(cur -> right);
                leaf = 0;
            }

            if(!leaf)
                nodes.push_back(cur);
        }

        for(int i = 0; i < nodes.size(); i++)
        {
            for(int j = i + 1; j < nodes.size(); j++)
            {
                if(same(nodes[i], nodes[j]))
                    return 1;
            }
        }

        return 0;
    }
};
```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://github.com/getlost01/gfg-potd/discussions). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the [getlost01/gfg-potd](https://github.com/getlost01/gfg-potd) repository.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gl01.gitbook.io/gfg-editorials/2023/10-2023-oct-11/12-duplicate-subtree-in-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.