function to return parent node

[peachslasher]

Hi guys,

I am trying to write C++ method to return a pointer to the parent of a particular node in binary tree, and for the root that doesn't have a parent should return NULL.

Here is my program so far:

#include <iostream>

using namespace std;

class Tree {
private:
  int data;
  //int count;
  Tree *leftptr, *rightptr;
  bool lthread, rthread;  // two new variables
public:
  Tree (int newthings, Tree *L, Tree *R);
  ~Tree(){ }
  int RootData(){ return data;}
  //int counting(){return count;}
  Tree *Left(){ return leftptr;}
  Tree *Right(){ return rightptr;} 
  //Tree *parent(Tree *T);
  bool isEmpty(){ if(leftptr == NULL && rightptr==NULL){cout << "ok" << endl; return true;} return false;}
};


Tree::Tree(int newthings, Tree *L, Tree *R){
  data = newthings;
  //count = n;
  leftptr = L;
  rightptr = R;
  //lthread = lt;
  //rthread = rt;
}

Tree *parent(Tree *T,Tree *parenttree){
  if(T == NULL) { return NULL;} //if the node is empty return
  //if the node is parent tree
  if(T == parenttree){
    return T;
  }
  if(T < parenttree){
	 cout << "The tree with: " <<T->RootData() << " is the child of tree with value of: " << parenttree->RootData() << endl;
    return parent(T->Left(), parenttree);
  }
  
  if(T > parenttree){
  cout << "The tree with: " <<T->RootData() << " is the child of tree with value of: " << parenttree->RootData() << endl;
  return parent(T->Right(), parenttree);
	}
}


void recuinorder(Tree *T){
  if(T == NULL){ return;}
  cout << "Reccrusive inorder function" << endl;
  recuinorder(T->Left());
  cout << T->RootData() << endl;
  recuinorder(T->Right());
}

void Tree::Insert(int item) {
// BST must already contain at least one item
  if (item > data) {  // move to the right
     if (rightptr == NULL) {
        rightptr = new Tree(item, NULL, NULL);
     } else {
        rightptr->Insert(item);
     }
  } else if (item < data) {  // move to the left
     if (leftptr == NULL) {
        leftptr = new Tree(item, NULL, NULL);
     } else {
        leftptr->Insert(item);
     }
  } else if (item == data) {  // should be unique
    cout << "Error: key is not unique" << endl;
     exit(9);
  }
}

int main(){
  Tree *a,*b,*mytree, *c;
  c = new Tree(16,NULL,NULL);
  a = new Tree(18,c,NULL);
  b = new Tree(30, NULL,NULL);
  mytree= new Tree(20,a,b);
  parent(c, mytree);
  //cout << << endl;
 
 }

The program seems to work only when the 3 consist of 3 nodes e.g parent(a,mytree). but when theres extra leaf(s) or child under sub tree it doesn't work.

I would be really great if you can show me how to find the parent node of the node that is belong under subtree for e.g node c

Thanks heaps =D

[VernonDozier]

Hi guys,

I am trying to write C++ method to return a pointer to the parent of a particular node in binary tree, and for the root that doesn't have a parent should return NULL.

Here is my program so far:

#include <iostream>

using namespace std;

class Tree {
private:
  int data;
  //int count;
  Tree *leftptr, *rightptr;
  bool lthread, rthread;  // two new variables
public:
  Tree (int newthings, Tree *L, Tree *R);
  ~Tree(){ }
  int RootData(){ return data;}
  //int counting(){return count;}
  Tree *Left(){ return leftptr;}
  Tree *Right(){ return rightptr;} 
  //Tree *parent(Tree *T);
  bool isEmpty(){ if(leftptr == NULL && rightptr==NULL){cout << "ok" << endl; return true;} return false;}
};


Tree::Tree(int newthings, Tree *L, Tree *R){
  data = newthings;
  //count = n;
  leftptr = L;
  rightptr = R;
  //lthread = lt;
  //rthread = rt;
}

Tree *parent(Tree *T,Tree *parenttree){
  if(T == NULL) { return NULL;} //if the node is empty return
  //if the node is parent tree
  if(T == parenttree){
    return T;
  }
  if(T < parenttree){
	 cout << "The tree with: " <<T->RootData() << " is the child of tree with value of: " << parenttree->RootData() << endl;
    return parent(T->Left(), parenttree);
  }
  
  if(T > parenttree){
  cout << "The tree with: " <<T->RootData() << " is the child of tree with value of: " << parenttree->RootData() << endl;
  return parent(T->Right(), parenttree);
	}
}


void recuinorder(Tree *T){
  if(T == NULL){ return;}
  cout << "Reccrusive inorder function" << endl;
  recuinorder(T->Left());
  cout << T->RootData() << endl;
  recuinorder(T->Right());
}

void Tree::Insert(int item) {
// BST must already contain at least one item
  if (item > data) {  // move to the right
     if (rightptr == NULL) {
        rightptr = new Tree(item, NULL, NULL);
     } else {
        rightptr->Insert(item);
     }
  } else if (item < data) {  // move to the left
     if (leftptr == NULL) {
        leftptr = new Tree(item, NULL, NULL);
     } else {
        leftptr->Insert(item);
     }
  } else if (item == data) {  // should be unique
    cout << "Error: key is not unique" << endl;
     exit(9);
  }
}

int main(){
  Tree *a,*b,*mytree, *c;
  c = new Tree(16,NULL,NULL);
  a = new Tree(18,c,NULL);
  b = new Tree(30, NULL,NULL);
  mytree= new Tree(20,a,b);
  parent(c, mytree);
  //cout << << endl;
 
 }

The program seems to work only when the 3 consist of 3 nodes e.g parent(a,mytree). but when theres extra leaf(s) or child under sub tree it doesn't work.

I would be really great if you can show me how to find the parent node of the node that is belong under subtree for e.g node c

Thanks heaps =D

I'm having difficulty visualizing how this tree works. In particular, i don't understand what the parent function is supposed to return and what arguments it takes. I would also change the word Tree to Node since it's a little confusing, at least to me. Looks to me like mytree is the root, a is the left child of mytree, and c is the left child of a. You want:

parent(c, mytree);

to return a since a is the parent of c, right? One thing you can't do is this:

if(T < parenttree)

T and parenttree are of type Tree, so you need to provide a comparison operator, which I don't see here. I assume you want to compare the data attributes of T and parenttree, then decide whether to go left or right to get from parenttree to T. If so, you need to access that data member, which is private, so if you want to keep parent as a non Tree class member function, you'll need to write an accessor function.

[EDIT]
Looks like you have an accessor function called RootData that returns value. I would change it to GetData or something more obvious.
[/EDIT]

[che-burator]

There's my version of returning the parent node:

Tree* findParent(Tree *t,int data){
    if(data==t->data){
        return NULL;//because this is the root
    }else
        if((t->left!=NULL && data==t->left->data ) || ( t->right!=NULL && data==t->right->data)){
            return t;
        }else
            if(data<t->data){
                return findParent(t->left,data);
            }
            else
            if(data>t->data){
                return findParent(t->right,data);
            }

}

It really works:)