Find next right node of a given key | Set 2 | C ++ program to find next right of a given key using preorder traversal ; A Binary Tree Node ; Utility function to create a new tree node ; Function to find next node for given node in same level in a binary tree by using pre - order traversal ; return null if tree is empty ; if desired node is found , set value_level to current level ; if value_level is already set , then current node is the next right node ; recurse for left subtree by increasing level by 1 ; if node is found in left subtree , return it ; recurse for right subtree by increasing level by 1 ; Function to find next node of given node in the same level in given binary tree ; A utility function to test above functions ; Driver program to test above functions ; Let us create binary tree given in the above example
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { struct Node * left , * right ; int key ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return temp ; } Node * nextRightNode ( Node * root , int k , int level , int & value_level ) { if ( root == NULL ) return NULL ; if ( root -> key == k ) { value_level = level ; return NULL ; } else if ( value_level ) { if ( level == value_level ) return root ; } Node * leftNode = nextRightNode ( root -> left , k , level + 1 , value_level ) ; if ( leftNode ) return leftNode ; return nextRightNode ( root -> right , k , level + 1 , value_level ) ; } Node * nextRightNodeUtil ( Node * root , int k ) { int value_level = 0 ; return nextRightNode ( root , k , 1 , value_level ) ; } void test ( Node * root , int k ) { Node * nr = nextRightNodeUtil ( root , k ) ; if ( nr != NULL ) cout << " Next ▁ Right ▁ of ▁ " << k << " ▁ is ▁ " << nr -> key << endl ; else cout << " No ▁ next ▁ right ▁ node ▁ found ▁ for ▁ " << k << endl ; } int main ( ) { Node * root = newNode ( 10 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 6 ) ; root -> right -> right = newNode ( 5 ) ; root -> left -> left = newNode ( 8 ) ; root -> left -> right = newNode ( 4 ) ; test ( root , 10 ) ; test ( root , 2 ) ; test ( root , 6 ) ; test ( root , 5 ) ; test ( root , 8 ) ; test ( root , 4 ) ; return 0 ; }