Skip to content

Instantly share code, notes, and snippets.

@abhash24oct

abhash24oct/BST.Java

Last active October 3, 2017 03:06
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save abhash24oct/4c9c9f1d5b4c986de0e70f61416f0c7e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save abhash24oct/4c9c9f1d5b4c986de0e70f61416f0c7e to your computer and use it in GitHub Desktop.
Download ZIP
BinarySearchTree In java
Raw
BST.Java
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BST {
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public Node insertNode(Node root, int data) {
if (root == null) {
Node newNode = new Node(data);
root = newNode;
} else if (root.data >= data) {
root.left = insertNode(root.left, data);
} else {
root.right = insertNode(root.right, data);
}
return root;
}
public Node insertNodeUsingLoop(Node root, int data) {
if (root == null) {
Node newNode = new Node(data);
root = newNode;
} else if (root.data >data) {
if (root.left == null) {
Node newNode = new Node(data);
root.left = newNode;
} else {
Node temp = root.left;
Node prev=null;
char side='L';
while (temp != null) {
prev=temp;
if (temp.data > data) {
temp = temp.left;
side='L';
} else {
temp = temp.right;
side='R';
}
}
if(prev.data!=data){
Node newNode = new Node(data);
if(side=='L')
prev.left=newNode;
else
prev.right=newNode;
}
}
} else {
if (root.right == null) {
Node newNode = new Node(data);
root.right = newNode;
} else {
Node temp = root.right;
Node prev=null;
char side='R';
while (temp != null) {
prev=temp;
if (temp.data > data) {
temp = temp.left;
side='L';
} else {
temp = temp.right;
side='R';
}
}
if(prev.data!=data){
Node newNode = new Node(data);
// newNode = (side=='L' )? prev.left :prev.right;
if(side=='L')
prev.left=newNode;
else
prev.right=newNode;
}
}
}
return root;
}
public void printTree(Node root) {
if (root == null) {
return;
} else {
printTree(root.left);
System.out.print(root.data+" ");
printTree(root.right);
// System.out.println(root.data);
}
}
public boolean search(Node root, int data) {
if (root == null) {
System.err.println("Not found");
return false;
}
if (root.data == data) {
System.out.println("Found");
return true;
}
if (root.data > data)
search(root.left, data);
else
search(root.right, data);
return false;
}
public static Node deleteNodeWithOneChild(Node delNode){
if(delNode.right!=null){
delNode=delNode.right;
}else{
delNode=delNode.left;
}
return delNode;
}
/**
* First we find the minimum in right subtree and delete the minimum node
* and then replace the node to be deleted with the min value
* @param root
* @return
*/
private Node deleteNodeWithTwoChild(Node root) {
int d = findMin(root.right);
this.delete(root, d);
root.data=d;
return root;
}
/**
* Three cases:
* 1) Node to be deleted is leaf: Simply remove from the tree.
* 2) Node to be deleted has only one child: Copy the child to the node and delete the child
*3) Node to be deleted has two children:
* @param root
* @param data
* @return
*/
public Node delete(Node root, int data){
if(root==null) return null;
if(root.data==data){
if(root.left !=null || root.right != null ){
if(root.left !=null && root.right!=null)
root=deleteNodeWithTwoChild(root);
else
root=deleteNodeWithOneChild(root);
}
else
root=null;
}
else if(root.data>data){
root.left=delete(root.left, data);
}else{
root.right=delete(root.right, data);
}
return root;
}
public int findMin(Node root){
if(root==null)
return -1;
else if(root.left==null )
return root.data;
return findMin(root.left);
}
Node maxNode=null;
public Node findMax(Node root){
Node temp=root;
if(root==null) return null;
else{
temp.right=findMax(root.right);
if(temp.left==null){
maxNode=temp;
}
}
return maxNode;
}
public int getMax(Node root){
if(root==null) return -1;
if(root.right==null){
return root.data;
}
return getMax(root.right);
}
/**
* Height will be 1 + max(heightof left subtree , height of right subtree)
*
* @param args
*/
public int findHeight(Node root){
if(root==null){
return -1;
}
System.out.println("before::"+root.data);
int leftHeight = findHeight(root.left);
System.out.println("LeftHeight ::"+leftHeight);
System.out.println("After ::"+root.data);
int rightHeight=findHeight(root.right);
System.out.println("RightHeight:: "+rightHeight);
return 1+ Math.max(leftHeight, rightHeight);
}
/**
*
* Level order traversal means traversing the tree level by level
* This is also called breadth first traversal
* we will use the queue to store the discovered nodes
* @param args
*/
public void levelOrderTraversal(Node root){
Queue<Node> q=new LinkedList<>();
q.add(root);
System.out.print("\n[ ");
while(!q.isEmpty()){
System.out.print(q.peek().data+",");
if(q.peek().left!=null) q.add(q.peek().left);
if(q.peek().right!=null) q.add(q.peek().right);
q.remove();
}
System.out.println("]");
}
public void preOrderTraversal(Node root){
if(root==null)
return;
System.out.print(root.data+",");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
public void postOrderTraversal(Node root){
if(root==null)
return;
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.data+",");
}
public void verticalUtil(Node root,int index,HashMap<Integer, Integer> hm){
if(root==null)
{
return;
}
else{
verticalUtil(root.left, index-1, hm);
if(hm.containsKey(index)){
System.out.println("repeated index"+index);
hm.put(index, hm.get(index)+root.data);
}else
hm.put(index, root.data);
verticalUtil(root.right, index+1, hm);
}
}
public void verticalSum(Node root){
HashMap<Integer, Integer> hm = new HashMap<>();
verticalUtil(root, 0, hm);
System.out.println();
System.out.println(hm);
// return 1;
}
public static void main(String[] args) {
Node root = null;
BST tree = new BST();
root = tree.insertNode(root, 16);
root = tree.insertNode(root, 17);
root = tree.insertNode(root, 8);
root = tree.insertNode(root, 10);
root = tree.insertNode(root, 9);
root = tree.insertNode(root, 11);
root = tree.insertNode(root, 2);
tree.printTree(root);
tree.search(root, 18);
// tree.search(root, 180);
// root=tree.delete(root, 8);
tree.printTree(root);
System.out.println("Max::"+tree.getMax(root));
tree.printTree(root);
tree.levelOrderTraversal(root);
tree.preOrderTraversal(root);
System.out.println("\nPostorder");
tree.postOrderTraversal(root);
// System.out.println("height finding");
// System.out.println("Height is "+tree.findHeight(root));
// tree.delete(root, 8);
System.out.println("\nPrinting tree after deletion");
tree.printTree(root);
System.out.println("\nPrinting tree after deletion 9");
tree.delete(root, 9);
tree.printTree(root);
tree.verticalSum(root);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment