Binary Tree: Given a binary tree, check if duplicate values are present

Problem Statement:

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      10
     *       / \    /  \
     *      2   9  11   14
     */

Output:

True

Solution Explanation:

We will use in order traversal to solve the problem.

While doing inorder traversal, add the node values into the set and compare with the new node values.

If its present return true, else add the node into the set and continue till the end of the tree.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <unordered_set>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

bool solution(Node* root, unordered_set<int> &s)
{

    if (root == NULL)
       return false;

    if (s.find(root->data) != s.end())
       return true;

    s.insert(root->data);
    
    return solution(root->left, s) || 
           solution(root->right, s);
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      10
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(10);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    unordered_set<int> s;

    cout<<solution(root, s);
    
    return 0;
}

Output

1