Binary Search Tree insert with Parent Pointer | C ++ program to demonstrate insert operation in binary search tree 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 ; Driver Program to test above functions ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 ; print iNoder traversal of the BST
#include <bits/stdc++.h> NEW_LINE struct Node { int key ; struct Node * left , * right , * parent ; } ; struct Node * newNode ( int item ) { struct Node * temp = new Node ; temp -> key = item ; temp -> left = temp -> right = NULL ; temp -> parent = NULL ; return temp ; } void inorder ( struct Node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; printf ( " Node ▁ : ▁ % d , ▁ " , root -> key ) ; if ( root -> parent == NULL ) printf ( " Parent ▁ : ▁ NULL ▁ STRNEWLINE " ) ; else printf ( " Parent ▁ : ▁ % d ▁ STRNEWLINE " , root -> parent -> key ) ; inorder ( root -> right ) ; } } struct Node * insert ( struct Node * node , int key ) { if ( node == NULL ) return newNode ( key ) ; if ( key < node -> key ) { Node * lchild = insert ( node -> left , key ) ; node -> left = lchild ; lchild -> parent = node ; } else if ( key > node -> key ) { Node * rchild = insert ( node -> right , key ) ; node -> right = rchild ; rchild -> parent = node ; } return node ; } int main ( ) { struct Node * 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 ) ; return 0 ; }