Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a binary search tree?
3.
Problem Statement
3.1.
Example
3.1.1.
Input
3.1.2.
Output
4.
Approach
4.1.
Algorithm
4.2.
C++ Implementation
4.3.
Java Implementation
4.4.
Python Implementation
4.5.
Output
4.6.
Time Complexity
4.7.
Space Complexity
5.
Application of Binary search tree
6.
Frequently Asked Questions
6.1.
What is a binary tree?
6.2.
What is a binary search tree?
6.3.
What is the time complexity for deleting a node in a binary search tree?
6.4.
What is the space complexity for deleting a node in a binary search tree?
6.5.
Is there any other way also to solve this problem?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Binary Search Tree | Iterative Delete

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

Introduction

Hey Ninjas, today we will read about a popular data structurebinary tree. It has a wide range of applications throughout various fields. Thus, it is also important when it comes to interviews with top tech companies. A mastery of binary trees could help us solve a lot of problems. In this article, we will be focusing on binary search trees

Binary Search Tree - Iterative Delete

What is a binary search tree?

A binary search tree (BST) is a data structure in which each node has at most two child nodes, left and right. The left child node holds a value less than or equal to its parent node, and the right child node holds a value greater than the parent node. This ordering property allows for efficient searching, insertion, and deletion of elements in the tree. 

In this article, we will look at one problem based on this data structure.

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

Problem Statement

We are given a binary search tree and also a node. The task is to delete the node from the binary search tree iteratively.

Recommended: Try this problem yourself before moving on to the solution. 

Example

Input

Let the BST be 2, 3, 4, 5, 6, 7 (Inorder Traversal).

Initial BST

You have to delete 3 from the BST. What will be the remaining BST?

Output

The In-order traversal of the remaining BST will be 2, 4, 5, 6, 7.

After deletion

Approach

There are some specific cases we have to handle while deleting the node in the binary search tree, so let's explore all the different cases:

Case 1:  If we have to delete a node that is a leaf node, then we can simply delete that node.

Explanation 1

Case 2: If we have to delete a node that has only one child. In this case, we simply swap the value of the child node with the current node and delete the child node, which is a leaf node.

Explanation 2

Case 3: If we have to delete a node with both children or an internal node. In that situation, first, we have to find the node's in-order successor. After this, we have to copy the value of the node's in-order successor to that particular node. Then we have to delete the in-order successor node. We can find the in-order successor for any element just by seeing the minimum element in the right subtree of that element.

Explanation 3

Algorithm

  • Check if the value to be deleted is present in the binary search tree. 
     
  • If the value is present in the binary search tree, check the number of children the node to be deleted has.
     
  • If the node to be deleted has either one child or 0 children, then use the following steps:
    • Make a new pointer of the tree node named as a new tree node that will replace the node to be deleted.
    • Check if the current node left child exists, then assign the new tree node pointer to the left of the current else, assign it to the right of the current. 
    • Now check whether the node to be deleted is the root, then return the new tree node from the function.
    • Now check which side of the previous the current node is attached. If it is attached to the left of the previous, then assign a new tree node to the left of the previous. Otherwise, to the right of the previous and last, delete the current.
       
  • If the node is to be deleted has two child nodes, then use the following steps to delete the node:
    • Compute the in-order successor for the node to be deleted
    • Before replacing the value, check if the parent node of the in-order successor is the current node or not. If it is not, then make the left child of the parent equal to the in-order successor of the right child. 
    • Else, if the inorder successor was itself the current, then make the right child of the node to be deleted equal to the right child of the inorder successor. 

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class node{
public:
    int data;
    node *left;
    node *right;
    node(int data){
        this->data = data;
        left = nullptr;
        right = nullptr;
    }
};

// Printing the nodes of tree using inorder traversal
void inorder(node *root){
    if (root != NULL){
        inorder(root->left);
        cout << root->data << ' ';
        inorder(root->right);
    }
}

// A new node insertion in binary search tree
node *insert(node *root, int key){

    // Check if the tree is null or empty then simply return the root value
    if (root == NULL){
        node *temp = new node(key);
        return temp;
    }
    if (key < root->data){

        /*
            If the key is less than root_data we have to insert the element
            in left subtree for that we will simply call the recursion in left
            subtree part
       */

        root->left = insert(root->left, key);
    }
    else{

        /*
            If the key is greater than root_data we have to insert the element
            in right subtree for that we will simply call the recursion in right
            subtree part
        */
        root->right = insert(root->right, key);
    }

    return root;
}

node *deleteNode(node *root, int value){

    // Current pointer to iterate
    node *stat = root;

    // One previous pointer from current
    node *prev = NULL;

    /*
        Iterating in binary search tree to check if the key with value
        data is actually present there or not
    */
    while (stat != NULL && stat->data != value){
        prev = stat;
        if (value < stat->data)
            stat = stat->left;
        else
            stat = stat->right;
    }

    if (stat == NULL){
        cout << "Value not found in BST" << endl;
        return root;
    }

    // Check if the node to be deleted has either 0 or 1 child
    if (stat->left == NULL || stat->right == NULL){

        // newtreenode with store the node to be deleted
        node *newtreenode;

        // check whether the node to be deleted has either 0 or 1 child
        if (stat->left == NULL)
            newtreenode = stat->right;
        else
            newtreenode = stat->left;

        /*
            check whether the node to be deleted is the root then simply return newtreenode
        */
        if (prev == NULL)
            return newtreenode;
        /*
            check the node to be deleted  is whether the previous nodes left or right and
            replace it with the newtreenode
        */
        if (stat == prev->left)
            prev->left = newtreenode;
        else
            prev->right = newtreenode;

        // simply delete the node
        delete stat;
    }

    // here node which has to be deleted has 2 child nodes
    else{
        node *prev = NULL;
        node *temp;

        // finding the inorder successor in case of node with 2 child nodes
        temp = stat->right;
        while (temp->left != NULL)
        {
            prev = temp;
            temp = temp->left;
        }

        /*
            before replacing the value check if the parent node of the inorder successor
            is the current node or not if it is not then make the left child of the parent
            equal to the inorder successor of the right child else if inorder successor was
            itself  the current then make the right child of the node to be deleted equal
            To the right child of inorder successor
        */
        prev != NULL ? prev->left = temp->right : stat->right = temp->right;

        stat->data = temp->data;
        delete temp;
    }
    return root;
}

int main()
{

    node *root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 6);
    root = insert(root, 7);

    cout << "Inorder traversal of original BST";
    cout << endl;
    inorder(root);
    cout << endl;

    // deleting the node having value as 3
    deleteNode(root, 3);
    cout << "Inorder traversal of new tree after deletion";
    cout << endl;
    inorder(root);
    cout << endl;

    return 0;
}

Java Implementation

class Node {
  int data;
  Node left;
  Node right;

  public Node(int data) {
    this.data = data;
  }
}

class  Main {
  Node root;

  public void deleteNodeIterative(int key) {
    Node current = root;
    Node parent = null;
    boolean isLeftChild = false;

    // Search for the node to be deleted
    while (current != null && current.data != key) {
      parent = current;
      if (key < current.data) {
        isLeftChild = true;
        current = current.left;
      } else {
        isLeftChild = false;
        current = current.right;
      }
    }

    // If node not found
    if (current == null) {
      System.out.println("Node with key " + key + " not found");
      return;
    }

    // If node has no children
    if (current.left == null && current.right == null) {
      if (current == root) {
        root = null;
      } else if (isLeftChild) {
        parent.left = null;
      } else {
        parent.right = null;
      }
    }
    // If node has only one child
    else if (current.right == null) {
      if (current == root) {
        root = current.left;
      } else if (isLeftChild) {
        parent.left = current.left;
      } else {
        parent.right = current.left;
      }
    } else if (current.left == null) {
      if (current == root) {
        root = current.right;
      } else if (isLeftChild) {
        parent.left = current.right;
      } else {
        parent.right = current.right;
      }
    }
    // If node has two children
    else {
      Node successor = getSuccessor(current);
      if (current == root) {
        root = successor;
      } else if (isLeftChild) {
        parent.left = successor;
      } else {
        parent.right = successor;
      }
      successor.left = current.left;
    }
  }

  public Node getSuccessor(Node node) {
    Node current = node.right;
    Node successor = null;
    Node successorParent = null;

    while (current != null) {
      successorParent = successor;
      successor = current;
      current = current.left;
    }

    if (successor != node.right) {
      successorParent.left = successor.right;
      successor.right = node.right;
    }
    return successor;
  }

  // Insertion Method
  public void insert(int data) {
    Node newNode = new Node(data);
    if (root == null) {
      root = newNode;
      return;
    }
    Node current = root;
    Node parent = null;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;
        if (current == null) {
          parent.left = newNode;
          return;
        }
      } else {
        current = current.right;
        if (current == null) {
          parent.right = newNode;
          return;
        }
      }
    }
  }

  public void inorderTraversal(Node node) {
    if (node != null) {
      inorderTraversal(node.left);
      System.out.print(node.data + " ");
      inorderTraversal(node.right);
    }
  }

  public static void main(String[] args) {
    Main bst = new Main();
    bst.insert(5);
    bst.insert(3);
    bst.insert(2);
    bst.insert(4);
    bst.insert(6);
    bst.insert(7);

    System.out.println("Inorder traversal before deletion:");
    bst.inorderTraversal(bst.root);

    int key = 3;
    bst.deleteNodeIterative(key);

    System.out.println("\nInorder traversal after deletion of key " + key + ":");
    bst.inorderTraversal(bst.root);
  }
}

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Printing the nodes of tree using inorder traversal
def inorder(root):
    if root != None:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

# A new node insertion in binary search tree
def insert(root, key):
    if root == None:
        return Node(key)
    if key < root.data:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

# First we will be  Iterating in binary search tree to 
# check if the key with value data is actually present 
# there or not. Then we will check the number of children 
# of the node and work accordingly 

def deleteNode(root, value):
    if root == None:
        print("Value not found in BST")
        return root
    if value < root.data:
        root.left = deleteNode(root.left, value)
    elif value > root.data:
        root.right = deleteNode(root.right, value)
    else:
        if root.left == None:
            temp = root.right
            return temp
        elif root.right == None:
            temp = root.left
            return temp
        temp = minValueNode(root.right)
        root.data = temp.data
        root.right = deleteNode(root.right, temp.data)
    return root

def minValueNode(node):
    current = node
    while(current.left != None):
        current = current.left
    return current

def main():
    root = None
    root = insert(root, 5)
    root = insert(root, 3)
    root = insert(root, 2)
    root = insert(root, 4)
    root = insert(root, 6)
    root = insert(root, 7)

    print("Inorder traversal of the given tree")
    inorder(root)

    # deleting node having value 3
    root = deleteNode(root, 3)
    print("Inorder traversal of the modified tree")
    inorder(root)

if __name__ == '__main__':
    main()

Output

Output

Time Complexity

The time complexity is O(N). Deleting a node in the Binary search tree using the iterative method will cost O(N) time complexity, where ‘N’ is the number of nodes in the binary search tree. Since we are iterating only once on every node, it will cost linear time complexity.

Space Complexity

The space complexity for deleting a node in the Binary search tree using the iterative method will cost O(1). The reason behind this is we are not using extra space.

You can also read about insertion into bst.

Application of Binary search tree

Binary search trees (BSTs) are a type of data structure that can be used to efficiently store and retrieve data. They are commonly used in various applications, such as:

  • Searching for specific data in a large dataset: Because BSTs are organized in a way that allows for fast searching, they are often used to find specific data within a large dataset quickly.
     
  • Sorting data: By repeatedly removing the smallest (or largest) element from a BST, the data stored in the tree can be sorted in ascending (or descending) order.
     
  • Implementing dictionaries and sets: BSTs can be used to implement dictionaries and sets, where each element is stored as a key-value pair or just a key.
     
  • In databases, it is used as an indexing method.
     
  • In computer file systems, it is used as a method of organizing files and folders.
     
  • In some game development, it is used for pathfinding in games.

Overall, binary search trees are a powerful and efficient data structure that can be used to solve a wide variety of problems.

Must Read Recursive Binary Search.

Frequently Asked Questions

What is a binary tree?

A binary tree is a data structure where each node can have at most two child nodes (left and right). The topmost node is the root, and the leaf nodes have no children.

What is a binary search tree?

A binary search tree (BST) is a type of binary tree where each node has at most two child nodes. The key in each node must be greater than or equal to any key stored in its left sub-tree and less than or equal to any key stored in its right sub-tree.

What is the time complexity for deleting a node in a binary search tree?

The time complexity for deleting a node in a binary search tree is O(N).

What is the space complexity for deleting a node in a binary search tree?

The space complexity for deleting a node in a binary search tree is O(1).

Is there any other way also to solve this problem?

Yes, we can solve this problem using recursion also. The difference between the two approaches is that in the iterative approach, the space complexity is O(1), whereas in the recursive approach, it is O(N).

Conclusion

In this article, we learned the iterative method for deleting a node in a BST. We learned about the intuition and approach for this algorithm. We also learned about its implementation in popular programming languages and their complexity analysis. 

Check out our articles if you think this blog has helped you enhance your knowledge and want to learn more. Visit our website to read more such blogs. 

  1. Find the second largest element in BST  
  2. Check if an array represents Inorder of BST
  3. Row with the Maximum Number of 1’s  
  4. Median of All Nodes from a Given Range in a BST 
  5. Count of Smaller Numbers After Self 


Check out this problem - XOR Queries On Tree

For placement preparations, you must look at the problemsinterview experiences, and interview bundles. Enrol in our courses and refer to the mock tests and problems available; look at the Problem Sheets interview experiences, and interview bundle for placement preparations. You can also book an interview session with us.  

Consider our paid courses, however, to give your career a competitive advantage!

Happy Coding!

Previous article
Deletion in Binary Search Tree
Next article
Searching in BST
Live masterclass