Reverse alternate levels of a perfect binary tree | Java program to reverse alternate levels of a tree ; Base cases ; Swap subtrees if level is even ; Recur for left and right subtrees ( Note : left of root1 is passed and right of root2 in first call and opposite in second call . ; This function calls preorder ( ) for left and right children of root ; Inorder traversal ( used to print initial and modified trees ) ; A utility function to create a new node ; Driver program to test above functions
class Sol { static class Node { char key ; Node left , right ; } ; static void preorder ( Node root1 , Node root2 , int lvl ) { if ( root1 == null root2 == null ) return ; if ( lvl % 2 == 0 ) { char t = root1 . key ; root1 . key = root2 . key ; root2 . key = t ; } preorder ( root1 . left , root2 . right , lvl + 1 ) ; preorder ( root1 . right , root2 . left , lvl + 1 ) ; } static void reverseAlternate ( Node root ) { preorder ( root . left , root . right , 0 ) ; } static void printInorder ( Node root ) { if ( root == null ) return ; printInorder ( root . left ) ; System . out . print ( root . key + " ▁ " ) ; printInorder ( root . right ) ; } static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . left = temp . right = null ; temp . key = ( char ) key ; return temp ; } public static void main ( String args [ ] ) { Node root = newNode ( ' a ' ) ; root . left = newNode ( ' b ' ) ; root . right = newNode ( ' c ' ) ; root . left . left = newNode ( ' d ' ) ; root . left . right = newNode ( ' e ' ) ; root . right . left = newNode ( ' f ' ) ; root . right . right = newNode ( ' g ' ) ; root . left . left . left = newNode ( ' h ' ) ; root . left . left . right = newNode ( ' i ' ) ; root . left . right . left = newNode ( ' j ' ) ; root . left . right . right = newNode ( ' k ' ) ; root . right . left . left = newNode ( ' l ' ) ; root . right . left . right = newNode ( ' m ' ) ; root . right . right . left = newNode ( ' n ' ) ; root . right . right . right = newNode ( ' o ' ) ; System . out . print ( "Inorder Traversal of given treeNEW_LINE"); printInorder ( root ) ; reverseAlternate ( root ) ; System . out . print ( " Inorder Traversal of modified tree "); printInorder ( root ) ; } }