Binary Search Tree(BST)

Binary Search Tree(BST)

 Binary search tree is either empty or satisfy rules.

BST(Binary Search tree)
  1. The value of a key in a left child or left subtree is less than the value of root.
  2. The value of a key in the right child or right subtree is greater than the value of the root.

Creation of Binary Tree

Create a Binary Search Tree
Data given : 40   60   50   33   55   11

Create binary tree

Search a node from BST

  • We begin by examining the root node.
  • If the value equal to root, the search is successful.
  • If the value is less than the root, search the left subtree.
  • If the value is greater than the root, search the right subtree.
  • The process is repeated until the value is found or the remaining subtree is NULL.

Algorithm for Searching Technique

BST Search(root,value)

  1. temp=root
  2. while(temp!=NULL)repeat 2 and 3
    if(temp->data=value)
    printf(“sucessful search”)
  3. Else if value data temp->temp->left
  4. Else temp=temp->right

Inserting a node in BST

Insert 16

Inserting element in binary tree

Algorithm for inserting a node

  1. Start from the root node.
  2. If the value to be inserted is X, compare this value with the root node.
  3. Equal step because value already exists.
  4. Less-than value of root/choose left subtree
  5. Greater-than value of root /choose right subtree,
  6. Repeat step 2 until the leaf node is encountered where data to be inserted.

Binary Search tree deletion of element

Steps:

  1. Search a node to remove.
  2. If node is found, call remove algorithm

Case 1:Node to be removed has no children

Case 2:Node to be removed has one child

Case 3:Node to be removed has two children

  • Find the minimun value in the right subtree.
  • Replace value of node to be removed with found minimimum value
  • Apply remove to the right subtree to remove duplicacy

Example 2:

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top