Binary Search Tree | CrackEase

Searching in Binary Search tree

In this page we discuss basic BST operations in C: insertion, deletion and inorder traversal. In a Binary Search Tree (BST) every node's left subtree contains values less than the node's key and the right subtree contains values greater than the node's key. Given a BST and a key, you can efficiently check whether the key exists in the tree.

Algorithm : How to search in Binary Search Tree ?

If tree is empty return (not found).
Compare key with root's key.
If key < root->key go to left subtree; if > go to right subtree.
If equal, key is found.

Code for Searching / Inserting / Deleting in BST

  
#include <stdio.h>
#include <stdlib.h>

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

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    inorder(root->left);
    printf("%d -> ", root->key);
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);
  return node;
}

// Find the inorder successor (smallest in the right subtree)
struct node *minValueNode(struct node *node) {
  struct node *current = node;
  while (current && current->left != NULL)
    current = current->left;
  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  if (root == NULL) return root;
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }
    struct node *temp = minValueNode(root->right);
    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 32);
  root = insert(root, 11);
  root = insert(root, 64);
  root = insert(root, 7);
  root = insert(root, 14);
  root = insert(root, 14); // duplicate insertion is allowed in this example
  root = insert(root, 6);

  printf("Inorder traversal: ");
  inorder(root);

  printf("\nAfter deleting 7\n");
  root = deleteNode(root, 7);
  printf("Inorder traversal: ");
  inorder(root);

  return 0;
}

  
#include <iostream>
#include <cstdlib>
using namespace std;

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

struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(struct node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " -> ";
    inorder(root->right);
  }
}

struct node *insert(struct node *node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);
  return node;
}

struct node *minValueNode(struct node *node) {
  struct node *current = node;
  while (current && current->left != NULL)
    current = current->left;
  return current;
}

struct node *deleteNode(struct node *root, int key) {
  if (root == NULL) return root;
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }
    struct node *temp = minValueNode(root->right);
    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 32);
  root = insert(root, 11);
  root = insert(root, 64);
  root = insert(root, 7);
  root = insert(root, 14);
  root = insert(root, 14);
  root = insert(root, 6);

  cout << "Inorder traversal: ";
  inorder(root);

  cout << "\nAfter deleting 7\n";
  root = deleteNode(root, 7);
  cout << "Inorder traversal: ";
  inorder(root);
  return 0;
}

  
class BinarySearchTree {
  class Node {
    int key;
    Node left, right;

    public Node(int item) {
      key = item;
      left = right = null;
    }
  }

  Node root;

  BinarySearchTree() { root = null; }

  void insert(int key) { root = insertKey(root, key); }

  Node insertKey(Node root, int key) {
    if (root == null) return new Node(key);
    if (key < root.key) root.left = insertKey(root.left, key);
    else root.right = insertKey(root.right, key);
    return root;
  }

  void inorder() { inorderRec(root); }

  void inorderRec(Node root) {
    if (root != null) {
      inorderRec(root.left);
      System.out.print(root.key + " -> ");
      inorderRec(root.right);
    }
  }

  void deleteKey(int key) { root = deleteRec(root, key); }

  Node deleteRec(Node root, int key) {
    if (root == null) return root;
    if (key < root.key) root.left = deleteRec(root.left, key);
    else if (key > root.key) root.right = deleteRec(root.right, key);
    else {
      if (root.left == null) return root.right;
      else if (root.right == null) return root.left;
      root.key = minValue(root.right);
      root.right = deleteRec(root.right, root.key);
    }
    return root;
  }

  int minValue(Node root) {
    int minv = root.key;
    while (root.left != null) {
      minv = root.left.key;
      root = root.left;
    }
    return minv;
  }

  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    tree.insert(8); tree.insert(32); tree.insert(11); tree.insert(64);
    tree.insert(7); tree.insert(14); tree.insert(14); tree.insert(6);

    System.out.print("Inorder traversal: ");
    tree.inorder();

    System.out.println("\nAfter deleting 7");
    tree.deleteKey(7);
    System.out.print("Inorder traversal: ");
    tree.inorder();
  }
}

Output : C/C++

	
Inorder traversal: 6 -> 7 -> 8 -> 11 -> 14 -> 14 -> 32 -> 64 -> 
After deleting 7
Inorder traversal: 6 -> 8 -> 11 -> 14 -> 14 -> 32 -> 64 ->

Output : Java

	
Inorder traversal: 6 -> 7 -> 8 -> 11 -> 14 -> 14 -> 32 -> 64 -> 
After deleting 7
Inorder traversal: 6 -> 8 -> 11 -> 14 -> 14 -> 32 -> 64 ->

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Searching in Binary Search tree

Searching in Binary Search tree