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 prvar inorder traversal using parent pointer ; Start traversal from root ; If left child is not traversed , find the leftmost child ; Prvar 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 { constructor ( key ) { this . key = key ; this . left = this . right = this . parent = null ; } } var root = null ; function insert ( node , 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 ; } function inorder ( root ) { var leftdone = false ; while ( root != null ) { if ( ! leftdone ) { while ( root . left != null ) { root = root . left ; } } document . write ( 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 ; } } root = insert ( root , 24 ) ; root = insert ( root , 27 ) ; root = insert ( root , 29 ) ; root = insert ( root , 34 ) ; root = insert ( root , 14 ) ; root = insert ( root , 4 ) ; root = insert ( root , 10 ) ; root = insert ( root , 22 ) ; root = insert ( root , 13 ) ; root = insert ( root , 3 ) ; root = insert ( root , 2 ) ; root = insert ( root , 6 ) ; document . write ( " " ) ; inorder ( root ) ;