Create a binary search tree

Implementation

In this section of the article, we will see the usage and mechanism of how we will create a given binary tree. Let's observe these in more depth and then we will see the implementation of the same in different languages and understand the concept more vividly.

Example 1)

// we will now observe binary search tree operations in different languages.
#include <iostream>
using namespace std;


struct nod {
  int ky;
  struct nod *Lft, *Rt;
};


// we have first to create a node for the binary tree.
struct nod *nwNod(int itm) {
  struct nod *temp = (struct nod *)malloc(sizeof(struct nod));
  temp->ky = itm;
  temp->Lft = temp->Rt = NILL;
  return temp;
}


// now, we will observe the in-order traversal for the tree.
void in order(struct nod *root) {
  if (root != NILL) {
    // traversing the tree in the left order.
    inorder(root->Lft);


    // traversing the tree in the root
    cout << root->ky << " -> ";


    // traversing the tree in the right order.
    inorder(root->Rt);
  }
}


// inserting a new node in the tree.
struct nod *insert(struct nod *nod, int ky) {
  // we have to return a new node if the tree is clear or empty.
  if (nod == NILL) return nwNod(ky);


  // then, we must move or traverse to the right place and slip the new node.
  if (ky < nod->ky)
    nod->Lft = insert(nod->Lft, ky);
  else
    nod->Rt = insert(nod->Rt, ky);


  return nod;
}


// look for the in-order successor.
struct nod *minValueNod(struct nod *nod) {
  struct nod *current = nod;


  // look for the leftmost leaf or node.
  while (current && current->Lft != NILL)
    current = current->Lft;


  return current;
}


// now, we will see how to delete a specific node.
struct nod *deleteNod(struct nod *root, int ky) {
  // we have to clear the space if the tree is found to be empty.
  if (root == NILL) return root;


  // look for the node which is supposed to be deleted.
  if (ky < root->ky)
    root->Lft = deleteNod(root->Lft, ky);
  else if (ky > root->ky)
    root->Rt = deleteNod(root->Rt, ky);
  else {
    // In case the node has no child or a single child, then: -
    if (root->Lft == NILL) {
      struct nod *temp = root->Rt;
      free(root);
      return temp;
    } else if (root->Rt == NILL) {
      struct nod *temp = root->Lft;
      free(root);
      return temp;
    }


    // In case the node has two children
    struct nod *temp = minValueNod(root->Rt);


    // now, we have to fix the in-order successor in a position where it is supposed to be fixed.
    root->ky = temp->ky;


    // eliminate the following
    root->Rt = deleteNod(root->Rt, temp->ky);
  }
  return root;
}


// writing the main code.
int main() {
  struct nod *root = NILL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);


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


  cout << "\nAfter deleting 10\n";
  root = deleteNod(root, 10);
  cout << "Inorder traversal: ";
  inorder(root);
}

Output:

Example 2)

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


struct nod {
  int ky;
  struct nod *Lft, *Rt;
};
// we have first to create a node for the binary tree.
struct nod *nwNod(int itm) {
  struct nod *temp = (struct nod *)malloc(sizeof(struct nod));
  temp->ky = itm;
  temp->Lft = temp->Rt = NILL;
  return temp;
}
// now, we will observe the in-order traversal for the tree.
void in order(struct nod *root) {
  if (root != NILL) {
    // traversing the tree in the left order.


    inorder(root->Lft);


    // traversing the tree in the root
    printf("%d -> ", root->ky);
    // traversing the tree in the right order.
    inorder(root->Rt);
  }
}
// inserting a new node in the tree.
struct nod *insert(struct nod *nod, int ky) {
  // we have to return a new node if the tree is clear or empty.
  if (nod == NILL) return nwNod(ky);
  // then, we must move or traverse to the right place and slip the new node.
  if (ky < nod->ky)
    nod->Lft = insert(nod->Lft, ky);
  else
    nod->Rt = insert(nod->Rt, ky);


  return nod;
}
// look for the in-order successor.
struct nod *minValueNod(struct nod *nod) {
  struct nod *current = nod;
  // look for the leftmost leaf or node.
  while (current && current->Lft != NILL)
    current = current->Lft;


  return current;
}
// now, we will see how to delete a specific node.
struct nod *deleteNod(struct nod *root, int ky) {
  // we have to clear the space if the tree is found to be empty.
  if (root == NILL) return root;
  // look for the node which is supposed to be deleted.
  if (ky < root->ky)
    root->Lft = deleteNod(root->Lft, ky);
  else if (ky > root->ky)
    root->Rt = deleteNod(root->Rt, ky);


  else {
    // In case the node has no child or a single child, then: -
    if (root->Lft == NILL) {
      struct nod *temp = root->Rt;
      free(root);
      return temp;
    } else if (root->Rt == NILL) {
      struct nod *temp = root->Lft;
      free(root);
      return temp;
    }
    // now, we have to fix the in-order successor in a position where it is supposed to be fixed.
    root->ky = temp->ky;
    // eliminate the following
    root->Rt = deleteNod(root->Rt, temp->ky);
  }
  return root;
}
// writing the main code.
int main() {
  struct nod *root = NILL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);


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


  printf("\nAfter deleting 10\n");
  root = deleteNod(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

Output:

Example 3)

class BinarySearchTree {
  class Nod {
    int ky;
    Nod Lft, Rt;


    public Nod(int itm) {
      ky = itm;
      Lft = Rt = NILL;
    }
  }


  Nod root;


  BinarySearchTree() {
    root = NILL;
  }


  void insert(int ky) {
    root = insertKy(root, ky);
  }
// inserting a new key in the tree.
  Nod insertKy(Nod root, int ky) {
  // we have to return a new node if the tree is clear or empty.
    if (root == NILL) {
      root = new Nod(ky);
      return root;
    }
  // then, we must move or traverse to the right place and slip the new node.
    if (ky < root.ky)
      root.Lft = insertKy(root.Lft, ky);
    else if (ky > root.ky)
      root.Rt = insertKy(root.Rt, ky);


    return root;
  }


  void inorder() {
    inorderRec(root);
  }
// look for the in-order successor.
  void inorderRec(Nod root) {
    if (root != NILL) {
      inorderRec(root.Lft);
      System.out.print(root.ky + " -> ");
      inorderRec(root.Rt);
    }
  }


  void deleteKy(int ky) {
    root = deleteRec(root, ky);
  }


  Nod deleteRec(Nod root, int ky) {
  // we have to clear the space if the tree is found to be empty.
    if (root == NILL)
      return root;
  // look for the node which is supposed to be deleted.
    if (ky < root.ky)
      root.Lft = deleteRec(root.Lft, ky);
    else if (ky > root.ky)
      root.Rt = deleteRec(root.Rt, ky);
    else {
    // In case the node has no child or a single child, then: -
      if (root.Lft == NILL)
        return root.Rt;
      else if (root.Rt == NILL)
        return root.Lft;


    // In case the node has two children
    // now, we have to fix the in-order successor in a position where it is supposed to be fixed.
      root.ky = minValue(root.Rt);


fixed.
    // eliminate the following
      root.Rt = deleteRec(root.Rt, root.ky);
    }


    return root;
  }
// look for the in-order successor.
  int minValue(Nod root) {
    int minv = root.ky;
    while (root.Lft != NILL) {
      minv = root.Lft.ky;
      root = root.Lft;
    }
    return minv;
  }
// writing the main code.
  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();


    tree.insert(8);
    tree.insert(3);
    tree.insert(1);
    tree.insert(6);
    tree.insert(7);
    tree.insert(10);
    tree.insert(14);
    tree.insert(4);


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


    System.out.println("\n\nAfter deleting 10");
    tree.deleteKy(10);
    System.out.print("Inorder traversal: ");
    tree.inorder();
  }
}

Output:

Example 4)

# we have first to create a node for the binary tree.
class Nod:
    def __init__(self, ky):
        self.ky = ky
        self.Lft = None
        self.Rt = None




# now, we will observe the in-order traversal for the tree.
def inorder(root):
    if the root is None:
        # traversing the tree in the left order.
        inorder(root.Lft)


        # traversing the tree in the root
        print(str(root.ky) + "->", end=' ')


        # traversing the tree in the right order.
        inorder(root.Rt)




# inserting a new node in the tree.
def insert(nod, ky):


    # we have to return a new node if the tree is clear or empty.
    If nod is None:
        return Nod(ky)


    # then, we must move or traverse to the right place and slip the new node.
    if ky < nod.ky:
        nod.Lft = insert(nod.Lft, ky)
    else:
        nod.Rt = insert(nod.Rt, ky)


    return nod




# look for the in-order successor.
def minValueNod(nod):
    current = nod


    # look for the leftmost leaf or node.
    while(current.Lft is not None):
        current = current.Lft


    return current




# now, we will see how to delete a specific node.
def deleteNod(root, ky):


    # we have to clear the space if the tree is found to be empty.
    if the root is None:
        return root


    # look for the node which is supposed to be deleted.
    if ky < root.ky:
        root.Lft = deleteNod(root.Lft, ky)
    elif(ky > root.ky):
        root.Rt = deleteNod(root.Rt, ky)
    else:
        # In case the node has no child or a single child, then: -


        if root.Lft is None:
            temp = root.Rt
            root = None
            return temp


        elif root.Rt is None:
            temp = root.Lft
            root = None
            return temp


        # In case the node has two children
        # now, we have to fix the in-order successor in a position that is supposed to be fixed.
        temp = minValueNod(root.Rt)


        root.ky = temp.ky


        # eliminate the following
        root.Rt = deleteNod(root.Rt, temp.ky)


    return root




root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 4)


print("Inorder traversal: ", end=' ')
inorder(root)


print("\nDelete 10")
root = deleteNod(root, 10)
print("Inorder traversal: ", end=' ')
inorder(root)

Output: