Find right sibling of a binary tree with parent pointers | C program to print right sibling of a node ; A Binary Tree Node ; A utility function to create a new Binary Tree Node ; Method to find right sibling ; GET Parent pointer whose right child is not a parent or itself of this node . There might be case when parent has no right child , but , current node is left child of the parent ( second condition is for that ) . ; Move to the required child , where right sibling can be present ; find right sibling in the given subtree ( from current node ) , when level will be 0 ; Iterate through subtree ; if no child are there , we cannot have right sibling in this path ; This is the case when we reach 9 node in the tree , where we need to again recursively find the right sibling ; Driver Program to test above functions ; passing 10
#include <bits/stdc++.h> NEW_LINE struct Node { int data ; Node * left , * right , * parent ; } ; Node * newNode ( int item , Node * parent ) { Node * temp = new Node ; temp -> data = item ; temp -> left = temp -> right = NULL ; temp -> parent = parent ; return temp ; } Node * findRightSibling ( Node * node , int level ) { if ( node == NULL node -> parent == NULL ) return NULL ; while ( node -> parent -> right == node || ( node -> parent -> right == NULL && node -> parent -> left == node ) ) { if ( node -> parent == NULL node -> parent -> parent == NULL ) return NULL ; node = node -> parent ; level -- ; } node = node -> parent -> right ; if ( node == NULL ) return NULL ; while ( level < 0 ) { if ( node -> left != NULL ) node = node -> left ; else if ( node -> right != NULL ) node = node -> right ; else break ; level ++ ; } if ( level == 0 ) return node ; return findRightSibling ( node , level ) ; } int main ( ) { Node * root = newNode ( 1 , NULL ) ; root -> left = newNode ( 2 , root ) ; root -> right = newNode ( 3 , root ) ; root -> left -> left = newNode ( 4 , root -> left ) ; root -> left -> right = newNode ( 6 , root -> left ) ; root -> left -> left -> left = newNode ( 7 , root -> left -> left ) ; root -> left -> left -> left -> left = newNode ( 10 , root -> left -> left -> left ) ; root -> left -> right -> right = newNode ( 9 , root -> left -> right ) ; root -> right -> right = newNode ( 5 , root -> right ) ; root -> right -> right -> right = newNode ( 8 , root -> right -> right ) ; root -> right -> right -> right -> right = newNode ( 12 , root -> right -> right -> right ) ; Node * res = findRightSibling ( root -> left -> left -> left -> left , 0 ) ; if ( res == NULL ) printf ( " No ▁ right ▁ sibling " ) ; else printf ( " % d " , res -> data ) ; return 0 ; }