Wednesday 8 August 2012

In a binary tree given any node, trace its path from root node.


//set equal=0 before calling trace function.

int equal=0;
void trace(node *r,int item)
{
      if(equal==1)
            return;

      if(r->data==item)
            equal=1;
      if(r!=NULL)
      {
            trace(r->left,item);
            trace(r->right,item);
            if(equal==1)
                  cout<<"  "<<r->data;
      }
}
Posted by at

4 comments:

  1. ROCKFORT8 January 2013 at 11:50

    it wont print the trace... it will just say whether the node is present or not!!
    correct me if i m wrong

    ReplyDelete
  2. Varun13 January 2013 at 06:01

    By trace I meant print the path from root node to the given node.
    10
    20 30
    40 50 60 70
    80 90

    In above example to path to reach 90 from root (10) is:
    90 -> 40 -> 20 -> 10

    ReplyDelete
  3. yash4 August 2013 at 05:05

    void trace(node *r,int path[],int pathLen,int item)
    {

    if(root ==NULL)
    return;

    path[pathLen] = root->dara;
    pathLen++;

    if(root->left == NULL && root->right == NULL)
    printArray(path,pathLen)
    else
    {
    trace(r->left,path,pathLen,item);
    trace(r->right,item,path,pathLen,item);
    }

    }

    void printArray(int path[],int pathLen)
    {
    for(int i =0;i<pathLen;i++)
    cout <<path[i];
    }

    ReplyDelete
  4. yash4 August 2013 at 05:13

    sorry above algo for all possible path from root to leaf . if you want to trace the path for any specific item you will add one extra check
    if( root-data == item)
    {
    printArray(path,pathLen);

    }

    ReplyDelete

Subscribe to: Post Comments (Atom)