Introduction
The BST or binary Search tree is a fundamental data structure. It implements other abstract data structures like sets, multisets, etc. It is more efficient than a standard binary tree.
The problem of binary search tree insertion with a parent pointer is a medium difficulty problem. We will use an inorder traversal and insertion approach to solve this problem. Make sure to try this problem on your own before reading this article.
Problem Statement
You are a knight of the Nightâ€™s watch. You are entrusted with the responsibility to take care of the wall. While guarding the wall, you come across a box that is locked. It can be opened if you successfully solve the puzzle. In the puzzle, you are given a BST. You have to do the insertion of a node. But the condition is the parent pointer needs to be maintained.
Your mate, Samwise Tarley, has a little knowledge of BST. And now you both are trying to solve the puzzle.
Letâ€™s understand this problem with the help of an example.
Sample Examples
Example 1: Node to be inserted: 35
Input:
Output:
Explanation: We inserted the leaf node 35 by keeping all the values of the parent node value as it is.
Example 2: Node to be inserted: 55
Input:
Output:
Explanation: We inserted the leaf node 55 by keeping all the values of the parent node value as it is.
Inorder traversal and Insertion Approach
During recursive calls for simple insertion, we return the pointer of the subtree's root created in a subtree. Here the idea is to store this pointer for left and right subtrees. After executing the recursive call operation, we set the parent pointers of these returned pointers. This will make sure that all parent pointers are set during insertion. The parent value of the root is set to NULL. We handle this by default assigning the parent as NULL to all newly allocated nodes.
Letâ€™s see the algorithm of the abovediscussed approach.
Algorithm
 We will first create a function to add a new node.

Now we will create a utility function to insert new nodes with a given key in BST. We will be facing three conditions:
 When the tree is empty, we will return a new node.

Otherwise, we will recur down the tree
 And first, set the parent value of the root of the left subtree.
 Then we will set the parent value of the root of the right subtree.
 Now return the value of the node pointer.
 Now we will create a utility function to do an inorder traversal of BST. Here we will insert the nodes accordingly.
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
class Node
{
public:
int key;
Node *left, *right, *parent;
};
//Utility Function To Create New Node//
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp>key = item;
temp>left = temp>right = NULL;
temp>parent = NULL;
return temp;
}
//Utility Function to insert given node//
struct Node* insertnode(struct Node* node, int key)
{
// If tree is empty then return a new node
if (node == NULL) return newNode(key);
//Else recur down the tree
if (key < node>key)
{
Node *leftchild = insertnode(node>left, key);
node>left = leftchild;
// Set the parent value of root of left subtree
leftchild>parent = node;
}
else if (key > node>key)
{
Node *rightchild = insertnode(node>right, key);
node>right = rightchild;
// Set the parent value of root of right subtree
rightchild>parent = node;
}
// return the Node value
return node;
}
//Utility Function to inorder traversal//
void inordertrfxn(struct Node *root)
{
if (root != NULL)
{
inordertrfxn(root>left);
cout<<"Node Value : "<< root>key<<", ";
if (root>parent == NULL)
cout<<"Parent Value : NULL"<<endl;
else
cout<<"Parent Value : "<< root>parent>key<< endl;
inordertrfxn(root>right);
}
}
//Main Function//
int main()
{
FAST;
struct Node *root = NULL;
root = insertnode(root, 45);
insertnode(root, 25);
insertnode(root, 15);
insertnode(root, 35);
insertnode(root, 65);
insertnode(root, 55);
insertnode(root, 75);
//Inorder traversal of the tree
inordertrfxn(root);
return 0;
}
Output:
Time Complexity
The time complexity of the aboveused approach is O(n). The BST we create here can become unbalanced. In such a case, the BST structure is much similar to a linked list, and then we have to traverse each node for insert, search, and deletion operations.
Space Complexity
The space complexity of the aboveused approach is O(n). The tree size depends on the number of nodes inside it.
Must Read Recursive Binary Search.