Binary Search Tree insert with Parent Pointer | Node structure ; A utility function to create a new BST Node ; A utility function to do inorder traversal of BST ; 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 ; Set parent of root of left subtree ; Set parent of root of right subtree ; return the ( unchanged ) Node pointer ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 ; prvar iNoder traversal of the BST
class Node { constructor ( ) { this . key = 0 ; this . left = null ; this . right = null ; this . parent = null ; } } function newNode ( item ) { var temp = new Node ( ) ; temp . key = item ; temp . left = null ; temp . right = null ; temp . parent = null ; return temp ; } function inorder ( root ) { if ( root != null ) { inorder ( root . left ) ; document . write ( " " + root . key + " " ) ; if ( root . parent == null ) document . write ( " " ) ; else document . write ( " " + root . parent . key + " " ) ; inorder ( root . right ) ; } } function insert ( node , key ) { if ( node == null ) return newNode ( key ) ; if ( key < node . key ) { var lchild = insert ( node . left , key ) ; node . left = lchild ; lchild . parent = node ; } else if ( key > node . key ) { var rchild = insert ( node . right , key ) ; node . right = rchild ; rchild . parent = node ; } return node ; } var root = null ; root = insert ( root , 50 ) ; insert ( root , 30 ) ; insert ( root , 20 ) ; insert ( root , 40 ) ; insert ( root , 70 ) ; insert ( root , 60 ) ; insert ( root , 80 ) ; inorder ( root ) ;