Using binary search tree to find duplicates

Question

I have implemented binary search tree. My code is pretty simple.

struct Tree{
    Tree* left;
    Tree* right;
    int value;
};

Here i declared basic struct.

Tree* makenode(int val){

    Tree* tmp= new Tree;
    tmp->left=tmp->right=NULL;
    tmp->value=val;
    return tmp;
}

The function that creates another struct type Tree.

void setLeft(Tree* x,int val){
    x->left=makenode(val);
}

void setRight(Tree* x,int val){
    x->right=makenode(val);
}

void insertt(Tree *x,int val){

    while(1){
        if(val < x->value){
            if(x->left!=NULL){
                x=x->left;
            }else{
                setLeft(x,val);
                break;
            }
        }else{
            if(x->right!=NULL){
                x=x->right;
            }else{
                setRight(x,val);
                break;
            }
        }
    }

}

Loop throught the Tree and insert the value at the right place = sorting the tree while adding to it.

What is making trouble to me is this little function

void travel(Tree *x){

    if(x->left!=NULL){

        travel(x->left);
    }
    Tree *b;
    b=x->right;
    if(x->value == b->value){
        cout << "Duplicate is " << x->value << endl;
        return ;
    }
    cout << "Value is " << x->value << endl;

    if(x->right!=NULL){
        travel(x->right);
    }
}

It nicely prints values if i omit

Tree *b;
b=x->right;    
if(x->value == b->value){
                cout << "Duplicate is " << x->value << endl;
                return ;
 }

I want it to check the enxt value when its printing current value , it both are the same = we have duplicit. But it always crash my program. What is causing this? The sorting works , the only problem that could be here is behavior of recursion ,but i cant figure out what

I tried to remake it as

void travel(Tree *x, vector<int> &y){
    vector<int>::iterator it;
    if(x->left!=NULL){
        if( x->value == x -> left -> value){
            it=find( y.begin(), y.end(), x->value );
            if(it==y.end()){
                y.push_back(x->value);
            }

        }
        travel(x->left, y);
    }


    cout << "Value is " << x->value << endl;

    if(x->right!=NULL){
        if( x->value == x -> right -> value){
            it=find( y.begin(), y.end(), x->value );
            if(it==y.end()){
                y.push_back(x->value);
            }

        }
        travel(x->right,y);
    }

}

But with this main function

int main()
{
   vector<int> dups;


   Tree * node = makenode(55);
   insertt(node,99);
   insertt(node,5);
   insertt(node,99);
   insertt(node,100);
   insertt(node,13);
   insertt(node,99);
   insertt(node,55);

   travel(node,dups);

   printDup(dups);
    return 0;
}
and printDup

using namespace std;

void printDup( vector<int> &y){
    cout << "Duplicates are: ";
    for( int i = 0; i < y.size(); i++){
        cout << y[i] << " ";
    }

}

It only prints 99 , why doesnt the others values get pushed into vector? Also how could i remakte the travel function make more elegant?

Answer 1

Python Code

import json

class Node:
   def __init__(self, val=0):
      self.right = ''
      self.left = ''
      self.value = val


class Tree(Node):

   def addNode(self, tree, node, duplicates):
      if not tree:
         tree = node
      elif tree.value > node.value:
         if tree.left:
            tree.left = self.addNode(tree.left, node, duplicates)
         else:
            tree.left = node
      elif tree.value < node.value:
         if tree.right:
            tree.right = self.addNode(tree.right, node, duplicates)
         else:
            tree.right = node
      elif tree.value == node.value:
         duplicates.append(node.value)

      return tree



def buildTree():
   arr = [14, 15, 4, 9, 7, 18, 3, 5, 16, 20,4,17, 9, 14, 5]
   tree = Tree()
   duplicates = []

   for v in arr:
      node = Node(v)
      tree = tree.addNode(tree, node, duplicates)


   s = json.dumps(tree.__dict__, default=serialize)
   print(s)
   print(duplicates)


def serialize(obj):
    return obj.__dict__


if __name__ == '__main__':
   buildTree()

Answer 2

It only prints 99 , why doesnt the others values get pushed into vector?

After you inserted the values 55, 99, 5, 99, 100, 13, 99, 55 your tree looks like this:

           55
          /  \
         /    \
        /      \
       5        99
        \      /  \
         13   55   99
                     \
                     100
                    /
                  99

So your algorithm to find duplicates only identifies 99, beacuse you only check if a child node of a node has the same value as the node self.

Note the successor of a node in a subtree is the outer left node of its right child and the predecessor is the outer right node of its left child.

Adapt your code like this and use std::setto store the duplicates:

#include <set>

int outerleft( Tree *x )
{
    while ( x->left != nullptr ) x = x->left;
    return x->value;
}

int outerright( Tree *x )
{
    while ( x->right != nullptr ) x = x->right;
    return x->value;
}

void travel(Tree *x, std::set<int> &dups )
{
    if ( x->left != nullptr )
    {
        if ( x->value == outerright( x->left ) )
            dups.insert( x->value );
        travel( x->left, dups );
    }

    std::cout << "Value is " << x->value << std::endl;

    if ( x->right != nullptr )
    {
        if ( x->value == outerleft( x->right )  )
            dups.insert( x->value );
        travel( x->right, dups );
    }
}

void printDup( const std::set<int> &dups )
{
    std::cout << "Duplicates are: ";
    for( int v : dups )
        std::cout << v << " ";
}