Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem Statement 
1.2.
Sample Examples 
2.
In-order traversal and Insertion Approach 
2.1.
Algorithm 
2.2.
Implementation in C++
2.2.1.
Time Complexity 
2.2.2.
Space Complexity 
3.
Frequently Asked Questions 
3.1.
How many types of insertion are performed in a binary tree?
3.2.
What is the difference between a binary search tree and a binary tree?
3.3.
Can a binary search tree have duplicates?
4.
Conclusion 
Last Updated: Mar 27, 2024
Medium

Binary Search Tree Insertion with a Parent Pointer

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

introduction

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.

problem statement

Let’s understand this problem with the help of an example.

Sample Examples 

Example 1: Node to be inserted: 35

Input:

input

Output:

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:

input

Output:

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;
}

 

Output:

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions 

How many types of insertion are performed in a binary tree?

Two kinds of insertion operations can be performed in a binary tree. They are inserting a leaf node and inserting an internal node.

What is the difference between a binary search tree and a binary tree?

A Binary Search Tree or BST is an organized binary tree. It has a structured organization of nodes.  Here each subtree is also of that particular structure.

While a binary tree is a non-linear data structure. Here a node can have 0, 1 or at max 2 nodes. Each node consists of a right pointer, a left pointer, and a data element. 

Can a binary search tree have duplicates?

A BST does not have any duplicate values. Since there is no advantage of duplicates in a search tree,  searching one value in a BST can only result in a single value, not in two or more.

Conclusion 

This article briefly discussed the problem of binary search tree insertion with a parent pointer.

We hope that this blog has helped you enhance your knowledge about the problem to minimize the number of weakly connected nodes and if you would like to learn more, check out our articles Remove BST keys outside of the given rangeCheck if the graph can be divided into two cliquesMultistage GraphPrint BST keys in the given valid rangeMinimize the number of weakly connected nodesCount BST subtrees that lie in a given range and Convert BST to the Greatest Sum Tree. You can also refer to our guided path on the basics of java and many more on our Website.

 

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series. You can also participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy learning!

Previous article
Pairs with a given sum such that Pair Elements lie in different BSTs
Next article
Rank of an Element in a Stream
Live masterclass