CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to construct a Binary Search Tree and perform deletion and inorder traversal.ExplanationIn this program, we need to create a binary search tree, delete a node from the tree, and display the nodes of the tree by traversing the tree using inorder traversal. In inorder traversal, for a given node, first, we traverse the left child then root then right child (Left > Root > Right). In Binary Search Tree, all nodes which are present to the left of root will be less than root node and nodes which are present to the right will be greater than the root node. Insertion:
Deletion:
Algorithm
SolutionPython#Represent a node of binary tree class Node: def __init__(self,data): #Assign data to the new node, set left and right children to None self.data = data; self.left = None; self.right = None; class BinarySearchTree: def __init__(self): #Represent the root of binary tree self.root = None; #insert() will add new node to the binary search tree def insert(self, data): #Create a new node newNode = Node(data); #Check whether tree is empty if(self.root == None): self.root = newNode; return; else: #current node point to root of the tree current = self.root; while(True): #parent keep track of the parent node of current node. parent = current; #If data is less than current's data, node will be inserted to the left of tree if(data < current.data): current = current.left; if(current == None): parent.left = newNode; return; #If data is greater than current's data, node will be inserted to the right of tree else: current = current.right; if(current == None): parent.right = newNode; return; #minNode() will find out the minimum node def minNode(self, root): if(root.left != None): return self.minNode(root.left); else: return root; #deleteNode() will delete the given node from the binary search tree def deleteNode(self, node, value): if(node == None): return None; else: #value is less than node's data then, search the value in left subtree if(value < node.data): node.left = self.deleteNode(node.left, value); #value is greater than node's data then, search the value in right subtree elif(value > node.data): node.right = self.deleteNode(node.right, value); #If value is equal to node's data that is, we have found the node to be deleted else: #If node to be deleted has no child then, set the node to None if(node.left == None and node.right == None): node = None; #If node to be deleted has only one right child elif(node.left == None): node = node.right; #If node to be deleted has only one left child elif(node.right == None): node = node.left; #If node to be deleted has two children node else: #then find the minimum node from right subtree temp = self.minNode(node.right); #Exchange the data between node and temp node.data = temp.data; #Delete the node duplicate node from right subtree node.right = self.deleteNode(node.right, temp.data); return node; #inorder() will perform inorder traversal on binary search tree def inorderTraversal(self, node): #Check whether tree is empty if(self.root == None): print("Tree is empty"); return; else: if(node.left != None): self.inorderTraversal(node.left); print(node.data, end=" "); if(node.right != None): self.inorderTraversal(node.right); bt = BinarySearchTree(); #Add nodes to the binary tree bt.insert(50); bt.insert(30); bt.insert(70); bt.insert(60); bt.insert(10); bt.insert(90); print("Binary search tree after insertion:"); #Displays the binary tree bt.inorderTraversal(bt.root); #Deletes node 90 which has no child deletedNode = bt.deleteNode(bt.root, 90); print("\nBinary search tree after deleting node 90:"); bt.inorderTraversal(bt.root); #Deletes node 30 which has one child deletedNode = bt.deleteNode(bt.root, 30); print("\nBinary search tree after deleting node 30:"); bt.inorderTraversal(bt.root); #Deletes node 50 which has two children deletedNode = bt.deleteNode(bt.root, 50); print("\nBinary search tree after deleting node 50:"); bt.inorderTraversal(bt.root); Output: Binary search tree after insertion: 10 30 50 60 70 90 Binary search tree after deleting node 90: 10 30 50 60 70 Binary search tree after deleting node 30: 10 50 60 70 Binary search tree after deleting node 50: 10 60 70 C#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //Represent a node of binary tree struct node{ int data; struct node *left; struct node *right; }; //Represent the root of binary tree struct node *root= NULL; //createNode() will create a new node struct node* createNode(int data){ //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); //Assign data to newNode, set left and right children to NULL newNode>data= data; newNode>left = NULL; newNode>right = NULL; return newNode; } //insert() will add new node to the binary search tree void insert(int data) { //Create a new node struct node *newNode = createNode(data); //Check whether tree is empty if(root == NULL){ root = newNode; return; } else { //current node point to root of the tree struct node *current = root, *parent = NULL; while(true) { //parent keep track of the parent node of current node. parent = current; //If data is less than current's data, node will be inserted to the left of tree if(data < current>data) { current = current>left; if(current == NULL) { parent>left = newNode; return; } } //If data is greater than current's data, node will be inserted to the right of tree else { current = current>right; if(current == NULL) { parent>right = newNode; return; } } } } } //minNode() will find out the minimum node struct node* minNode(struct node *root) { if (root>left != NULL) return minNode(root>left); else return root; } //deleteNode() will delete the given node from the binary search tree struct node* deleteNode(struct node *node, int value) { if(node == NULL){ return NULL; } else { //value is less than node's data then, search the value in left subtree if(value < node>data) node>left = deleteNode(node>left, value); //value is greater than node's data then, search the value in right subtree else if(value > node>data) node>right = deleteNode(node>right, value); //If value is equal to node's data that is, we have found the node to be deleted else { //If node to be deleted has no child then, set the node to NULL if(node>left == NULL && node>right == NULL) node = NULL; //If node to be deleted has only one right child else if(node>left == NULL) { node = node>right; } //If node to be deleted has only one left child else if(node>right == NULL) { node = node>left; } //If node to be deleted has two children node else { //then find the minimum node from right subtree struct node *temp = minNode(node>right); //Exchange the data between node and temp node>data = temp>data; //Delete the node duplicate node from right subtree node>right = deleteNode(node>right, temp>data); } } return node; } } //inorder() will perform inorder traversal on binary search tree void inorderTraversal(struct node *node) { //Check whether tree is empty if(root == NULL){ printf("Tree is empty\n"); return; } else { if(node>left!= NULL) inorderTraversal(node>left); printf("%d ", node>data); if(node>right!= NULL) inorderTraversal(node>right); } } int main() { //Add nodes to the binary tree insert(50); insert(30); insert(70); insert(60); insert(10); insert(90); printf("Binary search tree after insertion: \n"); //Displays the binary tree inorderTraversal(root); struct node *deletedNode = NULL; //Deletes node 90 which has no child deletedNode = deleteNode(root, 90); printf("\nBinary search tree after deleting node 90: \n"); inorderTraversal(root); //Deletes node 30 which has one child deletedNode = deleteNode(root, 30); printf("\nBinary search tree after deleting node 30: \n"); inorderTraversal(root); //Deletes node 50 which has two children deletedNode = deleteNode(root, 50); printf("\nBinary search tree after deleting node 50: \n"); inorderTraversal(root); return 0; } Output: Binary search tree after insertion: 10 30 50 60 70 90 Binary search tree after deleting node 90: 10 30 50 60 70 Binary search tree after deleting node 30: 10 50 60 70 Binary search tree after deleting node 50: 10 60 70 JAVApublic class BinarySearchTree { //Represent a node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinarySearchTree(){ root = null; } //insert() will add new node to the binary search tree public void insert(int data) { //Create a new node Node newNode = new Node(data); //Check whether tree is empty if(root == null){ root = newNode; return; } else { //current node point to root of the tree Node current = root, parent = null; while(true) { //parent keep track of the parent node of current node. parent = current; //If data is less than current's data, node will be inserted to the left of tree if(data < current.data) { current = current.left; if(current == null) { parent.left = newNode; return; } } //If data is greater than current's data, node will be inserted to the right of tree else { current = current.right; if(current == null) { parent.right = newNode; return; } } } } } //minNode() will find out the minimum node public Node minNode(Node root) { if (root.left != null) return minNode(root.left); else return root; } //deleteNode() will delete the given node from the binary search tree public Node deleteNode(Node node, int value) { if(node == null){ return null; } else { //value is less than node's data then, search the value in left subtree if(value < node.data) node.left = deleteNode(node.left, value); //value is greater than node's data then, search the value in right subtree else if(value > node.data) node.right = deleteNode(node.right, value); //If value is equal to node's data that is, we have found the node to be deleted else { //If node to be deleted has no child then, set the node to null if(node.left == null && node.right == null) node = null; //If node to be deleted has only one right child else if(node.left == null) { node = node.right; } //If node to be deleted has only one left child else if(node.right == null) { node = node.left; } //If node to be deleted has two children node else { //then find the minimum node from right subtree Node temp = minNode(node.right); //Exchange the data between node and temp node.data = temp.data; //Delete the node duplicate node from right subtree node.right = deleteNode(node.right, temp.data); } } return node; } } //inorder() will perform inorder traversal on binary search tree public void inorderTraversal(Node node) { //Check whether tree is empty if(root == null){ System.out.println("Tree is empty"); return; } else { if(node.left!= null) inorderTraversal(node.left); System.out.print(node.data + " "); if(node.right!= null) inorderTraversal(node.right); } } public static void main(String[] args) { BinarySearchTree bt = new BinarySearchTree(); //Add nodes to the binary tree bt.insert(50); bt.insert(30); bt.insert(70); bt.insert(60); bt.insert(10); bt.insert(90); System.out.println("Binary search tree after insertion:"); //Displays the binary tree bt.inorderTraversal(bt.root); Node deletedNode = null; //Deletes node 90 which has no child deletedNode = bt.deleteNode(bt.root, 90); System.out.println("\nBinary search tree after deleting node 90:"); bt.inorderTraversal(bt.root); //Deletes node 30 which has one child deletedNode = bt.deleteNode(bt.root, 30); System.out.println("\nBinary search tree after deleting node 30:"); bt.inorderTraversal(bt.root); //Deletes node 50 which has two children deletedNode = bt.deleteNode(bt.root, 50); System.out.println("\nBinary search tree after deleting node 50:"); bt.inorderTraversal(bt.root); } } Output: Binary search tree after insertion: 10 30 50 60 70 90 Binary search tree after deleting node 90: 10 30 50 60 70 Binary search tree after deleting node 30: 10 50 60 70 Binary search tree after deleting node 50: 10 60 70 C#using System; namespace Tree { public class Program { //Represent a node of binary tree public class Node<T>{ public T data; public Node<T> left; public Node<T> right; public Node(T data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } public class BinarySearchTree<T> where T : IComparable<T>{ //Represent the root of binary tree public Node<T> root; public BinarySearchTree(){ root = null; } //insert() will add new node to the binary search tree public void insert(T data) { //Create a new node Node<T> newNode = new Node<T>(data); //Check whether tree is empty if(root == null){ root = newNode; return; } else { //current node point to root of the tree Node<T> current = root, parent = null; while(true) { //parent keep track of the parent node of current node. parent = current; //If data is less than current's data, node will be inserted to the left of tree if(data.CompareTo(current.data) < 0) { current = current.left; if(current == null) { parent.left = newNode; return; } } //If data is greater than current's data, node will be inserted to the right of tree else { current = current.right; if(current == null) { parent.right = newNode; return; } } } } } //minNode() will find out the minimum node public Node<T> minNode(Node<T> root) { if (root.left != null) return minNode(root.left); else return root; } //deleteNode() will delete the given node from the binary search tree public Node<T> deleteNode(Node<T> node, T value) { if(node == null){ return null; } else { //value is less than node's data then, search the value in left subtree if(value.CompareTo(node.data) < 0) node.left = deleteNode(node.left, value); //value is greater than node's data then, search the value in right subtree else if(value.CompareTo(node.data) > 0) node.right = deleteNode(node.right, value); //If value is equal to node's data that is, we have found the node to be deleted else { //If node to be deleted has no child then, set the node to null if(node.left == null && node.right == null) node = null; //If node to be deleted has only one right child else if(node.left == null) { node = node.right; } //If node to be deleted has only one left child else if(node.right == null) { node = node.left; } //If node to be deleted has two children node else { //then find the minimum node from right subtree Node<T> temp = minNode(node.right); //Exchange the data between node and temp node.data = temp.data; //Delete the node duplicate node from right subtree node.right = deleteNode(node.right, temp.data); } } return node; } } //inorder() will perform inorder traversal on binary search tree public void inorderTraversal(Node<T> node) { //Check whether tree is empty if(root == null){ Console.WriteLine("Tree is empty"); return; } else { if(node.left!= null) inorderTraversal(node.left); Console.Write(node.data + " "); if(node.right!= null) inorderTraversal(node.right); } } } public static void Main() { BinarySearchTree<int> bt = new BinarySearchTree<int>(); //Add nodes to the binary tree bt.insert(50); bt.insert(30); bt.insert(70); bt.insert(60); bt.insert(10); bt.insert(90); Console.WriteLine("Binary search tree after insertion:"); //Displays the binary tree bt.inorderTraversal(bt.root); Node<int> deletedNode = null; //Deletes node 90 which has no child deletedNode = bt.deleteNode(bt.root, 90); Console.WriteLine("\nBinary search tree after deleting node 90:"); bt.inorderTraversal(bt.root); //Deletes node 30 which has one child deletedNode = bt.deleteNode(bt.root, 30); Console.WriteLine("\nBinary search tree after deleting node 30:"); bt.inorderTraversal(bt.root); //Deletes node 50 which has two children deletedNode = bt.deleteNode(bt.root, 50); Console.WriteLine("\nBinary search tree after deleting node 50:"); bt.inorderTraversal(bt.root); } } } Output: Binary search tree after insertion: 10 30 50 60 70 90 Binary search tree after deleting node 90: 10 30 50 60 70 Binary search tree after deleting node 30: 10 50 60 70 Binary search tree after deleting node 50: 10 60 70 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of binary tree class Node{ public $data; public $left; public $right; function __construct($data){ //Assign data to the new node, set left and right children to NULL $this>data = $data; $this>left = NULL; $this>right = NULL; } } class BinarySearchTree{ //Represent the root of binary tree public $root; function __construct(){ $this>root = NULL; } //insert() will add new node to the binary search tree function insert($data) { //Create a new node $newNode = new Node($data); //Check whether tree is empty if($this>root == NULL){ $this>root = $newNode; return; } else { //current node point to root of the tree $current = $this>root; $parent = NULL; while(true) { //parent keep track of the parent node of current node. $parent = $current; //If data is less than current's data, node will be inserted to the left of tree if($data < $current>data) { $current = $current>left; if($current == NULL) { $parent>left = $newNode; return; } } //If data is greater than current's data, node will be inserted to the right of tree else { $current = $current>right; if($current == NULL) { $parent>right = $newNode; return; } } } } } //minNode() will find out the minimum node function minNode($root) { if ($root>left != NULL) return $this>minNode($root>left); else return $root; } //deleteNode() will delete the given node from the binary search tree function deleteNode($node, $value) { if($node == NULL){ return NULL; } else { //value is less than node's data then, search the value in left subtree if($value < $node>data) $node>left = $this>deleteNode($node>left, $value); //value is greater than node's data then, search the value in right subtree else if($value > $node>data) $node>right = $this>deleteNode($node>right, $value); //If value is equal to node's data that is, we have found the node to be deleted else { //If node to be deleted has no child then, set the node to null if($node>left == NULL && $node>right == NULL) $node = NULL; //If node to be deleted has only one right child else if($node>left == NULL) { $node = $node>right; } //If node to be deleted has only one left child else if($node>right == NULL) { $node = $node>left; } //If node to be deleted has two children node else { //then find the minimum node from right subtree $temp = $this>minNode($node>right); //Exchange the data between node and temp $node>data = $temp>data; //Delete the node duplicate node from right subtree $node>right = $this>deleteNode($node>right, $temp>data); } } return $node; } } //inorder() will perform inorder traversal on binary search tree function inorderTraversal($node) { //Check whether tree is empty if($this>root == NULL){ print("Tree is empty <br>"); return; } else { if($node>left != NULL) $this>inorderTraversal($node>left); print("$node>data "); if($node>right != NULL) $this>inorderTraversal($node>right); } } } $bt = new BinarySearchTree(); //Add nodes to the binary tree $bt>insert(50); $bt>insert(30); $bt>insert(70); $bt>insert(60); $bt>insert(10); $bt>insert(90); print("Binary search tree after insertion: <br>"); //Displays the binary tree $bt>inorderTraversal($bt>root); //Deletes node 90 which has no child $deletedNode = $bt>deleteNode($bt>root, 90); print("<br>Binary search tree after deleting node 90: <br>"); $bt>inorderTraversal($bt>root); //Deletes node 30 which has one child $deletedNode = $bt>deleteNode($bt>root, 30); print("<br>Binary search tree after deleting node 30: <br>"); $bt>inorderTraversal($bt>root); //Deletes node 50 which has two children $deletedNode = $bt>deleteNode($bt>root, 50); print("<br>Binary search tree after deleting node 50: <br>"); $bt>inorderTraversal($bt>root); ?> </body> </html> Output: Binary search tree after insertion: 10 30 50 60 70 90 Binary search tree after deleting node 90: 10 30 50 60 70 Binary search tree after deleting node 30: 10 50 60 70 Binary search tree after deleting node 50: 10 60 70
Next TopicPrograms List
