### Siblings of a BST Node Algorithm?

I'm working on an implementation of a Binary Search Tree and I'm having trouble in printing the sibling of a node in BST

Can anyone guide me towards the correct algorithm for this?

Here's my code

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176`` ``````#include #include using namespace std; struct BST { int data; BST *left, *right; BST* CreateNode(int dat) { BST *temp = new BST(); temp->data = dat; temp->left = temp->right = NULL; return temp; } void inorder(BST *root) { if (root == NULL) { return; } inorder(root->left); cout << root->data << " "; inorder(root->right); } BST* insert(BST* ptr, int dat) { if (ptr == NULL){ return (CreateNode(dat)); } if (dat < ptr->data) ptr->left = insert(ptr->left, dat); else if (dat > ptr->data) ptr->right = insert(ptr->right, dat); return ptr; } int leaf(BST *Ptr) { if (Ptr == NULL) { return 0; } if (Ptr->left == NULL && Ptr->right == NULL) { return 1; } else { return (leaf(Ptr->left) + leaf(Ptr->right)); } } BST* Search(BST *Ptr, int dat) { if (Ptr == NULL) { return NULL; } if (Ptr->data == dat) { cout << "Found Node\n"; return Ptr; } if (dat < Ptr->data) { Ptr->left = Search(Ptr->left, dat); } if (dat > Ptr->data) { Ptr->right = Search(Ptr->right, dat); } return Ptr; } BST* MinNode(BST *Ptr) { //For Deleting while (Ptr->left != NULL) { Ptr = Ptr->left; } cout << "Min Node: " << Ptr->data << endl; return Ptr; } BST* Delete(BST *Ptr, int dat) { //Base Cases if (Ptr == NULL) { cout << "Value Doesn't Exist in Tree Can't Delete\n"; return Ptr; } if (Ptr->data == dat) { cout << "Found Node Deleting....\n"; //No Child Case if (Ptr->left == NULL && Ptr->right == NULL) { delete Ptr; cout << "Node With No Child Deleted...\n"; return NULL; } //One Child Case if (Ptr->right==NULL) { BST *tmpnode; tmpnode = Ptr->left; delete Ptr; cout << "Node with One child Deleted\n"; return tmpnode; } if (Ptr->left==NULL) { BST *tmpnode; tmpnode = Ptr->right; delete Ptr; cout << "Node with One child Deleted\n"; return tmpnode; } //Two Child Case if (Ptr->left && Ptr->right) { //Both Not NULL or both have values associated with them BST *tmpnode = NULL; tmpnode = MinNode(Ptr->right); Ptr->data = tmpnode->data; Ptr->right = Delete(Ptr->right, tmpnode->data); cout << "Node with 2 children deleted.....\n"; return Ptr; } } //Recursive Cases if (dat < Ptr->data) { Ptr->left = Delete(Ptr->left, dat); } if (dat>Ptr->data) { Ptr->right = Delete(Ptr->right, dat); } return Ptr; } bool PrintAncestors(BST *ptr,int dat) { //Base Cases if (ptr == NULL) { return false; } if (ptr->data == dat) { return true; } //Recursive Cases if (PrintAncestors(ptr->left, dat) || PrintAncestors(ptr->right, dat)) { cout << ptr->data << " "; return true; } return false; } }; int main() { BST Obj; BST *root = NULL; root = Obj.insert(root, 50); Obj.insert(root, 25); Obj.insert(root, 55); Obj.insert(root, 54); Obj.insert(root, 57); Obj.insert(root, 26); Obj.inorder(root); cout << endl; cout << Obj.leaf(root) << endl; Obj.Search(root, 57); cout << endl; Obj.MinNode(root); cout << endl; Obj.Delete(root, 55); cout << endl; Obj.inorder(root); cout << endl; cout << "Ancestors: "; Obj.PrintAncestors(root, 54); cout << endl; Obj.PrintSiblings(root,54); system("PAUSE"); return 0; }``````
Last edited on
It's a lot like search. The function returns true when it finds the value. When the caller sees a true return, he prints the sibling. The only tricky part is that the caller then returns false. In other words, the function only returns true when it finds the node with dat.

Here is the code. I have also changed inorder to print the structure of the tree so you can verify it.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198`` ``````#include #include using namespace std; struct BST { int data; BST *left, *right; BST* CreateNode(int dat) { BST *temp = new BST(); temp->data = dat; temp->left = temp->right = NULL; return temp; } void inorder(BST *root, int depth=0) { if (root == NULL) { return; } inorder(root->left, depth+1); for (int i=0; idata << '\n'; inorder(root->right, depth+1); } BST* insert(BST* ptr, int dat) { if (ptr == NULL){ return (CreateNode(dat)); } if (dat < ptr->data) ptr->left = insert(ptr->left, dat); else if (dat > ptr->data) ptr->right = insert(ptr->right, dat); return ptr; } int leaf(BST *Ptr) { if (Ptr == NULL) { return 0; } if (Ptr->left == NULL && Ptr->right == NULL) { return 1; } else { return (leaf(Ptr->left) + leaf(Ptr->right)); } } BST* Search(BST *Ptr, int dat) { if (Ptr == NULL) { return NULL; } if (Ptr->data == dat) { cout << "Found Node\n"; return Ptr; } if (dat < Ptr->data) { Ptr->left = Search(Ptr->left, dat); } if (dat > Ptr->data) { Ptr->right = Search(Ptr->right, dat); } return Ptr; } BST* MinNode(BST *Ptr) { //For Deleting while (Ptr->left != NULL) { Ptr = Ptr->left; } cout << "Min Node: " << Ptr->data << endl; return Ptr; } BST* Delete(BST *Ptr, int dat) { //Base Cases if (Ptr == NULL) { cout << "Value Doesn't Exist in Tree Can't Delete\n"; return Ptr; } if (Ptr->data == dat) { cout << "Found Node Deleting....\n"; //No Child Case if (Ptr->left == NULL && Ptr->right == NULL) { delete Ptr; cout << "Node With No Child Deleted...\n"; return NULL; } //One Child Case if (Ptr->right==NULL) { BST *tmpnode; tmpnode = Ptr->left; delete Ptr; cout << "Node with One child Deleted\n"; return tmpnode; } if (Ptr->left==NULL) { BST *tmpnode; tmpnode = Ptr->right; delete Ptr; cout << "Node with One child Deleted\n"; return tmpnode; } //Two Child Case if (Ptr->left && Ptr->right) { //Both Not NULL or both have values associated with them BST *tmpnode = NULL; tmpnode = MinNode(Ptr->right); Ptr->data = tmpnode->data; Ptr->right = Delete(Ptr->right, tmpnode->data); cout << "Node with 2 children deleted.....\n"; return Ptr; } } //Recursive Cases if (dat < Ptr->data) { Ptr->left = Delete(Ptr->left, dat); } if (dat>Ptr->data) { Ptr->right = Delete(Ptr->right, dat); } return Ptr; } bool PrintAncestors(BST *ptr,int dat) { //Base Cases if (ptr == NULL) { return false; } if (ptr->data == dat) { return true; } //Recursive Cases if (PrintAncestors(ptr->left, dat) || PrintAncestors(ptr->right, dat)) { cout << ptr->data << " "; return true; } return false; } bool PrintSiblings(BST *Ptr, int dat) { if (Ptr == NULL) { return false; } if (Ptr->data == dat) { return true; // only return true when you find it } if (dat < Ptr->data) { if(PrintSiblings(Ptr->left, dat) && Ptr->right) { cout << "Sibling of " << dat << ": " << Ptr->right-> data << '\n'; } } else { if (PrintSiblings(Ptr->right, dat) && Ptr->left) { cout << "Sibling of " << dat << ": " << Ptr->left->data << '\n'; } } return false; } }; int main() { BST Obj; BST *root = NULL; root = Obj.insert(root, 50); Obj.insert(root, 25); Obj.insert(root, 55); Obj.insert(root, 54); Obj.insert(root, 57); Obj.insert(root, 26); Obj.inorder(root); cout << endl; cout << Obj.leaf(root) << endl; Obj.Search(root, 57); cout << endl; Obj.MinNode(root); cout << endl; Obj.Delete(root, 55); cout << endl; Obj.inorder(root); cout << endl; cout << "Ancestors: "; Obj.PrintAncestors(root, 54); cout << endl; Obj.PrintSiblings(root,54); Obj.PrintSiblings(root,25); system("PAUSE"); return 0; }``````

Registered users can post here. Sign in or register to post.