Check if a Binary Tree has Duplicate Values

Introduction 

Checking if a binary tree has duplicate values is a basic binary tree problem. You will encounter this type of problem in DSA sheets that are quite trending nowadays. Alongside it is one of those problems that checks an individual's critical thinking and basic understanding by analyzing the most fundamental approach of the programmer.

In this article, we’ll solve the problem to check if a binary tree has duplicate values or not by using a hash table approach.

Problem Statement 

We are given a binary tree; we need to check if a binary tree has duplicate values or not.

Do remember that the binary tree is not a binary search tree.

Sample Examples 

Example 1:

Output:

Explanation: The left child of node ‘1’ and left child of node ‘2’ have equal values, i.e., 2, which means both have duplicate values.

Example 2:

Output:

Explanation: The root node ‘3’ and left child of node ‘4’ have equal values, i.e., 3, which means both have duplicate values.

Hash Table Approach 

In the problem to check if a binary tree has duplicate values, we are using a traversing and hash table approach. Here we traverse the given tree first, checking each node to see if it already exists in the hash table. We return true if it exists (found duplicate); else, if it doesn't exist, it is added to the hash table.

Algorithm

1. We are doing particularly two tasks to solve this program. The first step is going to be traversing the tree, and the second step is to create a hashing table.
2. After creating the hash table, start storing the values accordingly.
3. Now we will check whether the value of the hash table gets matched again or not.
4. If the values of the hash table are the same, then we will return that there is a duplicate value; else, we will return there is not any duplicate value.

Implementation 

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

class BSTNode {
public:
    int data;
    BSTNode* left;
    BSTNode* right;
    BSTNode() {};
};

BSTNode* newnode(int newdata) { 
     BSTNode *curr = new BSTNode; 
     curr->data = newdata; 
     curr->left = curr->right = nullptr;
     return curr;
 }
 
void print(BSTNode* root) {
      if (root != nullptr) 
     {
        print(root->left);
        cout << root->data << endl;
        print(root->right);
     }
}

bool checking(BSTNode* parent, int val) {
    if(parent == nullptr)   // point 1
        return false;
    if (val == parent->data){   // point 2
        return true;
    }
    else {
        bool left = checking(parent->left, val);
        bool right = checking(parent->right, val);
        return left||right;
    }
}

bool assist(BSTNode* parent) {
    if (parent != nullptr)
    {   
        if(checking(parent->left, parent->data)) return true;  // point 3
        if(checking(parent->right, parent->data)) return true;
        return assist(parent->left)||assist(parent->right);   // point 4
    }
    else return false;
}

int main() {

    BSTNode *test = newnode(1);
    test->left=newnode(2);
    test->right=newnode(3);
    test->left->left=newnode(2);
    test->right->right=newnode(5);

    print(test);


    if (assist(test))
        cout << "There is a duplicate value" << endl;
    else
        cout << "There is no duplicate value" << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output 

Time Complexity

Time complexity is O(n), as we are using the concept of traversing a binary tree here, where ‘n’ is the number of nodes in a binary tree.

Space Complexity

A hash table is used to store the value of the binary tree. So, the space complexity of our program is O(n).

Must Recommended Topic, Binary Tree Postorder Traversal.

Also check out - Inorder Predecessor