Find next right node of a given key | Set 2 | Java 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 [ 0 ] to current level ; if value [ 0 ] 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
import java . util . * ; class GfG { static class Node { Node left , right ; int key ; } static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = null ; temp . right = null ; return temp ; } static Node nextRightNode ( Node root , int k , int level , int [ ] value ) { if ( root == null ) return null ; if ( root . key == k ) { value [ 0 ] = level ; return null ; } else if ( value [ 0 ] != 0 ) { if ( level == value [ 0 ] ) return root ; } Node leftNode = nextRightNode ( root . left , k , level + 1 , value ) ; if ( leftNode != null ) return leftNode ; return nextRightNode ( root . right , k , level + 1 , value ) ; } static Node nextRightNodeUtil ( Node root , int k ) { int [ ] v = new int [ 1 ] ; v [ 0 ] = 0 ; return nextRightNode ( root , k , 1 , v ) ; } static void test ( Node root , int k ) { Node nr = nextRightNodeUtil ( root , k ) ; if ( nr != null ) System . out . println ( " Next ▁ Right ▁ of ▁ " + k + " ▁ is ▁ " + nr . key ) ; else System . out . println ( " No ▁ next ▁ right ▁ node ▁ found ▁ for ▁ " + k ) ; } public static void main ( String [ ] args ) { 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 ) ; } }