Friday, January 25, 2013

Finding Path in the tree


Below are the code used to find the path in the Tree

I have verified most of the cases , May be experts can give batter solution than this . As always suggestions are welcome

#include <iostream>
#include <conio.h>

using namespace std;
class node
{
public:
 int data ;
 node(int in)
 {data = in;
   left = NULL ;
   right = NULL;
 }
 node* left ;
 node* right;
};


node* findpathrootnode(int a ,int b ,node* root)
{
 if(root->data > a && root->data < b)
 {
  return root;
 }
 else
 {
  findpathrootnode(a,b,root->right);
 }
 
}

void findleftpath(int a ,node * root)
{
 if(root!= NULL &&  root->data > a)
    findleftpath(a,root->left);
 else if(root!= NULL && root->data < a)
   findleftpath(a,root->right);
 
   cout<<root->data << endl;

}

void findrightpath(int b , node * root)
{
 cout<<root->data<<endl;

 if(root!= NULL &&  root->data > b)
    findrightpath(b,root->left);
 else if(root!= NULL && root->data < b)
   findrightpath(b,root->right);

}


main()
 {

  node * obj1 = new node(5);
  node * obj2 = new node(6);
  node * obj3 = new node(4);
  node * obj4 = new node(7);
  node * obj5 = new node(8);
  node * obj6 = new node(9);

  // make tree

  obj1->left  = obj3;
  obj1->right = obj5;

  obj2->left = NULL;
  obj2->right = NULL;

  obj4->left = obj2;
  obj4->right = NULL;

  obj3->left = NULL;
  obj3->right = NULL;

  obj5->left = obj4;
  obj5->right = obj6;

  obj6->left = NULL;
  obj6->right = NULL;

  //tree in done

  node * newroot = findpathrootnode(4,7,obj1);
  findleftpath(4,newroot);
  findrightpath(7,newroot->right);
  getch();
 }

No comments:

Post a Comment