Inorder Non | BST node ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; Function to print inorder traversal using parent pointer ; Start traversal from root ; If left child is not traversed , find the leftmost child ; Print root 's data ; Mark left as done ; If right child exists ; If right child doesn 't exist, move to parent ; If this node is right child of its parent , visit parent 's parent first ; Driver Code
class Node { int key ; Node left , right , parent ; public Node ( int key ) { this . key = key ; left = right = parent = null ; } } class BinaryTree { Node root ; Node insert ( Node node , int key ) { if ( node == null ) return new Node ( key ) ; if ( key < node . key ) { node . left = insert ( node . left , key ) ; node . left . parent = node ; } else if ( key > node . key ) { node . right = insert ( node . right , key ) ; node . right . parent = node ; } return node ; } void inorder ( Node root ) { boolean leftdone = false ; while ( root != null ) { if ( ! leftdone ) { while ( root . left != null ) { root = root . left ; } } System . out . print ( root . key + " ▁ " ) ; leftdone = true ; if ( root . right != null ) { leftdone = false ; root = root . right ; } else if ( root . parent != null ) { while ( root . parent != null && root == root . parent . right ) root = root . parent ; if ( root . parent == null ) break ; root = root . parent ; } else break ; } } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = tree . insert ( tree . root , 24 ) ; tree . root = tree . insert ( tree . root , 27 ) ; tree . root = tree . insert ( tree . root , 29 ) ; tree . root = tree . insert ( tree . root , 34 ) ; tree . root = tree . insert ( tree . root , 14 ) ; tree . root = tree . insert ( tree . root , 4 ) ; tree . root = tree . insert ( tree . root , 10 ) ; tree . root = tree . insert ( tree . root , 22 ) ; tree . root = tree . insert ( tree . root , 13 ) ; tree . root = tree . insert ( tree . root , 3 ) ; tree . root = tree . insert ( tree . root , 2 ) ; tree . root = tree . insert ( tree . root , 6 ) ; System . out . println ( " Inorder ▁ traversal ▁ is ▁ " ) ; tree . inorder ( tree . root ) ; } }