1.
Introduction
1.1.
Problem Statement
1.2.
Samples Examples
2.
Deletion and Insertion Key Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
3.1.
In a binary tree, what is a leaf node?
3.2.
What is the BST in order traversal time complexity?
3.3.
What is the total time complexity of all values stored in an n-node binary search tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Implementing Decrease key in Binary Search Tree

## Introduction

A binary tree is a type of tree data structure. It contains a single root node and two disjoint subtrees called the left and the right subtree. The maximum degree of the node of a binary tree is 2. A binary search tree is a tree data structure that uses some order to arrange its elements, whereas a binary tree does not. You can visit our articles, Binary Tree and Binary Search Tree, to learn more about binary trees and BST.

This article will discuss the problem of implementing decrease key in BST. We will use the deletion and insertion key approach for implementing decrease key in BST.

### Problem Statement

The problem is of implementing decrease key in BST. We are given a BST. We will write a function that takes three arguments. The root of the tree, the old key value, and the new key value.

The function we make should change the old key value to the new key value. The function can assume that the old key value always exists in BST. Now, let’s understand the problem of implementing the  decrease key in BST with some examples.

### Samples Examples

Example 1:

Input: The root of the below tree.

Old key value: 35

New key value: 5

Output:

Updated BST

Example 2:

Input: The root of the below tree

Old key value: 72

New key value: 37

Output: Updated BST

Check out this problem - Mirror A Binary Tree

## Deletion and Insertion Key Approach

We have the deletion and insertion key approach for implementing the  decrease key in BST. The idea behind this approach is to call delete for the old key value. Then we will call insert for the new key value. Let’s see the algorithm for this approach.

### Algorithm

1. We will make a function to create a BST node.
2. Afterward, we will make a function to do an in-order traversal of BST.
3. Now create a function to insert a new node with a given key in BST. To do so, we will make two cases. First, if the tree is empty. Then return a new node. Otherwise, recur down the tree. And now, return the node pointer.
4. When we are provided with a non-empty binary search tree. We will return the node with the minimum key value found in that tree. The entire tree will not be searched.
5. If we are provided with a BST and a key. The function deletes the key and returns the new root.
1. If the key which will be deleted is smaller than the root's key, then it lies in the left subtree.
2. If the key which will be deleted is greater than the root's key, then it lies in the right subtree.
3. If the key is the same as the root's key, then that is the node supposed to be deleted.

### Implementation

``````// Program of implementing decrease key on bst
#include<bits/stdc++.h>
using namespace std;

struct node
{
int key;
node *left, *right;
};

// The function to create a new BST node
node *newNode(int element)
{
node *temp = new node;
temp->key = element;
temp->left = temp->right = NULL;
return temp;
}

// A function to do in order traversal of BST
void inordertraversal(node *rootnode)
{
if (rootnode != NULL)
{
inordertraversal(rootnode->left);
cout << rootnode->key << " ";
inordertraversal(rootnode->right);
}
}

// Given a non-empty bst, return the node with minimum key found in tree.
node * minimumValueNode(node* Node)
{
node* present= Node;

// looping down to find the leftmost leaf
while (present->left != NULL)
present= present->left;
return present;
}

// A function to insert a new node with given key in BST
node* insertkey(node* node, int key)
{
// If the tree is empty then we will return a new node
if (node == NULL)
return newNode(key);

// Otherwise we will recur down the tree
if (key < node->key)
node->left = insertkey(node->left, key);
else
node->right = insertkey(node->right, key);

return node;
}

// Given a bst and a key, this function deletes the key and returns the new root
node* deletenodekey(node* rootnode, int key)
{
if (rootnode == NULL)
return rootnode;

// Now if the key to be deleted is smaller than the root's key, then it lies in the left subtree
if (key < rootnode->key)
rootnode->left = deletenodekey(rootnode->left, key);

// And if the key to be deleted is greater than the root's key, then it lies in the right subtree
else if (key > rootnode->key)
rootnode->right = deletenodekey(rootnode->right, key);

// if the key is the same as root's key. Then the node to be deleted is
else
{
// node with only one or no child
if (rootnode->left == NULL)
{
node *tempvar = rootnode->right;
free(rootnode);
return tempvar;
}
else if (rootnode->right == NULL)
{
node *tempvar = rootnode->left;
free(rootnode);
return tempvar;
}

// node with two children. Here, Get the inorder successor (smallest in the right subtree)
node* tempvar = minimumValueNode(rootnode->right);

// Now Copy the inorder successor's content to this node
rootnode->key = tempvar->key;

// Delete the inorder successor
rootnode->right = deletenodekey(rootnode->right, tempvar->key);
}
return rootnode;
}

// The function to decrease a key value in Binary Search Tree
node *changingtheKey(node *rootnode, int oldVal, int newVal)
{
// First delete old key value
rootnode = deletenodekey(rootnode, oldVal);

// Then insert new key value
rootnode = insertkey(rootnode, newVal);

// Return new root
return rootnode;
}

int main()
{
int keys[] = { 45, 25, 15, 35, 65, 55, 75 };

node* rootnode = nullptr;
for (int key: keys) {
rootnode = insertkey(rootnode, key);
}

cout << "Inorder traversal of given tree \n";
inordertraversal(rootnode);

rootnode = changingtheKey(rootnode, 35, 5);

cout << "\nInorder traversal of the modified tree \n";
inordertraversal(rootnode);

return 0;
}``````

Output:

#### Time Complexity

The above approach's time complexity for implementing the decrease key in BST is O(h). Here h is the height of BST.

#### Space Complexity

The space complexity of the above approach for the problem implementing decrease key in BST is O(n). Here we used extra space to store nodesThe algorithm used for conversion has a linear space complexity. Hence, the space complexity of the approach is O(n).

### In a binary tree, what is a leaf node?

A node with two empty child nodes is called a leaf node. We say that the p node is the parent of the q node and that the q node is a child of the p node if the q node is the root of p's subtree and p is a node. Sibling nodes are two nodes with the same parents.

### What is the BST in order traversal time complexity?

Each node in an in-order tree traversal is only visited once if there are n nodes, so the complexity is O(n).

### What is the total time complexity of all values stored in an n-node binary search tree?

The time complexity of all values stored in an n-node binary search tree is O(n). As we know, there are n nodes in the tree, and we are calculating the maximum sum of the node-to-leaf paths of each node's left and right subtree. So it will take this much time.

## Conclusion

This article briefly discussed the problem of implementing decrease key in BST. We used the deletion and insertion key for implementing decrease key in BST.

We hope that this blog has helped you enhance your knowledge about the above question and if you like to learn more, check out our articles Maximum Width In Binary Tree and Special Binary Tree. Also, see Binary Tree Zigzag Traversal and Number of balanced binary trees.

You can also practice some relevant problems at the code studio, such as Preorder Binary TreeConstruct Binary Tree using Inorder and Preorder TraversalTop View Of Binary Tree, and Height of the Binary Tree From Inorder and Level Order Traversal.

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 and 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!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass