Binary Search Tree Insertion with a Parent Pointer

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 in-order 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.

In-order 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 above-discussed approach.

Algorithm 

1. We will first create a function to add a new node.
2. Now we will create a utility function to insert new nodes with a given key in BST. We will be facing three conditions:
   1. When the tree is empty, we will return a new node.
   2. Otherwise, we will recur down the tree
      1. And first, set the parent value of the root of the left subtree.
      2. Then we will set the parent value of the root of the right subtree.
   3. Now return the value of the node pointer.
3. Now we will create a utility function to do an in-order 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);

    //In-order traversal of the tree
		inordertrfxn(root);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity 

The time complexity of the above-used 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 above-used approach is O(n). The tree size depends on the number of nodes inside it.

Must Read Recursive Binary Search.