Binary Search Tree - Important Algorithms

Binary search tree - Wikipedia

Insertion in Binary Search Tree :
public treeNode insertNode(Node currentNode, int data) {
if(currentNode==null){
currentNode= new treeNode(data);
}
// data moves to right subtree
if(data>currentNode.data){
currentNode.right = insertNode(currentNode.right,data); 
}
//data moves to left subtree
else if(data<=currentNode.data){
currentNode.left = insertNode(currentNode.left,data);
}
return currentNode;
}


Deletion of a node in Binary Search Tree:

public  treeNode deleteNode(treeNode node, int data){
if(root==null) // tree is empty
return null;

if(data<node.data){
node.left = deleteNode(node.left,data);
}
else if(data>root.data){
node.right = deleteNode(node.right,data);
}
// if the current node has the data to delete, consider three cases - 0/1/2 child of current node

// if two child
// find the minimum of the right subtree and replace the current node
with the value found. Also delete the node with min value of the right subtree
// if one child
//If the only child is left child
if(node.left!=null){
node = node.left();
}
// if the only child is right child
else node = node.right();
// if no child
node = null;

return  node;
}

 Searching in Binary Search Tree:
public treeNode search(treeNode node, int data) {
if(node==null){
return  null;
}
if(data==node.data){
Print “found”
return node;
}
if(data<node.data){
 search(node.left, data);
}
else{
search(node.right,data);
}
}


Comments

Post a Comment

Popular posts from this blog

Quick Sort

According to me, it is the easiest and one of the most important and efficient sorting algorithm. Java 7 also uses quicksort for their .sort() method Time Complexity - O(nlogn) Space Complexity - O(n) -> As we are using recursion, it uses the internal stack In quicksort, we chose a pivot element first (in this program, I chose the last element as pivot) All the elements in any array, which are less than the pivot remains to the left of pivot and all the elements which are greater than the pivot element remains to the right of pivot. To do the above, we first chose last element as pivot element, i as (start-1) and j as start In quicksort, we only have to take care of pivot, i and j Now, we compare if a[i]<= pivot element. If yes, we increment i and swap arr[i] and arr[j] After completing one iteration from start to end, we get a pivot element fixed at its right position. Now, we recursively do this for the left subarray and right subarray to the pivot element. QuickS...
Read more

Disjoint Set - Implemented Using Arrays

Image
  What is a Disjoint Set? Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint set has mainly 3 Operations: makeset() -> makes 'n' number of disjoint sets containing single elements find(currentSet) -> returns the representative/parent of currentSet union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set.  Before going through code, I would recommend watching this video -  https://www.youtube.com/watch?v=wU6udHRIkcc Code: public class Mai...
Read more

Graph Traversal Code - BFS on Graph represented using Adjacency Matrix

Image
  import java.util.*; // A graph Node class GraphNode{     String name;     boolean isVisited;     //index is used to map this node with index of Adjacency Matrix     int index;      GraphNode(String name,int index){         this.name = name;         this.isVisited = false;         this.index = index;     }      } public class Main {          // A List to store the address of all the nodes of the graph     ArrayList<GraphNode> nodeList = new ArrayList<GraphNode>();     // An adjacency Matrix to store the details about which nodes are adjacent to each other (basically which two nodes has a edge between them)     int [][] adjacencyMatrix;          // Constructor     Main(ArrayList<GraphNode> nodeList){         this.nod...
Read more