Home » Data Structure

Check if the tree has duplicate value or not

In this article, we are going to see whether the tree has a duplicate value or not?
Submitted by Radib Kar, on August 12, 2020

Prerequisite:

• Level order traversal
• Hashing tutorial

To check whether the tree consists of duplicate values or not, the only way is to do any traversal and to store all values in a hash table. While traversing and adding if we find that the value is already present in the hash table, then that means that the tree has duplicate values. If even after the traversal finishes if we don't find any values repeating, then there are no duplicates in the tree.

Below is the two examples, where in the first tree there is a duplicate, but in the second example, there is no duplicate in the tree.

Examples:

1) A binary tree having duplicate

Figure 1: Example1 tree

In the above example, we can see that the tree has a duplicate value that is 1.

2) A binary tree without having duplicate

Figure 2: Example2 tree

In the above example, we can see that the tree has no duplicate values.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data)
    {
        val = data;
        left = NULL;
        right = NULL;
    }
};

bool isThereDuplicate(TreeNode* root)
{
    if (!root)
        return false;

    //do level order traversal and add 
    //the node values to hash table
    queue<TreeNode*> q;
    q.push(root);
    set<int> hash;
    
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        //if value already is hash, 
        //then duplicate found
        if (hash.find(cur->val) != hash.end())
            return true;
        hash.insert(cur->val);
        if (cur->left)
            q.push(cur->left);
        if (cur->right)
            q.push(cur->right);
    }

    return false;
}

int main()
{
    //building the tree like example 1
    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);
    root1->left->left = new TreeNode(1);

    if (isThereDuplicate(root1))
        cout << "Tree in example 1 has duplicate values\n";
    else
        cout << "Tree in example 1 doesn't have duplicate values\n";

    //building the tree-like example 2
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->right = new TreeNode(3);
    root2->left->left = new TreeNode(4);
    root2->left->right = new TreeNode(5);
    root2->right->right = new TreeNode(6);

    if (isThereDuplicate(root2))
        cout << "Tree in example 2 has duplicate values\n";
    else
        cout << "Tree in example 2 doesn't have duplicate values\n";

    return 0;
}

Output:

Tree in example 1 has duplicate values
Tree in example 2 doesn't have duplicate values

Dry run of examples:

As discussed we will do level order traversal and store the values in the hash table and check for the duplicate. To see detail on hash table and level order traversal, please check the prerequisite articles.

Example 1:

Iteration 1: After processing root 1

Iteration 2: After processing node 2

Iteration 3: After processing node 3

Iteration 4: After processing node 1

Here we find the duplicate in the tree.

Example 2:

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Iteration 6:

So, there is no single duplicate found.