ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to Check if a BST is a Balanced tree.

A balanced BST is a tree in which all the leaf nodes are at the same distance from the root node. It is not necessary that all leaf node be present but the distance between two leaf nodes should not be 1 or greater.

We can use this to check if a BST is balanced and then decide to or let the tree decide if it wants to become self balanced.
This is called self-balancing BST.

AVL , Red-black, Scapegoat trees are examples of self-balancing BST.

This is what excites me most about data structures one topic that leads to another.

import java.io.*;
import java.util.*;

class Node
{
	public int item;
	public Node leftChild;
	public Node rightChild;
	public void displayNode()
	{
		System.out.print("[");
		System.out.print(item);
		System.out.print("]");
	}
}
class StackNode
{
	public Node item;
	public StackNode next;
	public StackNode(Node val)
	{
		item = val;
	}

}
class LinkedListStack
{
	private StackNode first;
	public LinkedListStack()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(Node key)//inserts at beginning of list
	{
		StackNode newLLNode = new StackNode(key);
		newLLNode.next = first;
		first = newLLNode;
	}
	public Node delete()//deletes at beginning of list
	{
		StackNode temp = first;
		first = first.next;
		return temp.item;
	}
}
class Stack
{
	private LinkedListStack listObj;
	public Stack()
	{
		listObj = new LinkedListStack();
	}
	public void push(Node num)
	{
		listObj.insert(num);
	}
	public Node pop()
	{
		return listObj.delete();
	}
	public boolean isEmpty()
	{
		return listObj.isEmpty();
	}
}

class Tree
{
	public Node root;
	public Tree()
	{ root = null; }
	public Node returnRoot()
	{
		return root;
	}
	public void insert(int id)
	{
		Node newNode = new Node();
		newNode.item = id;
		if(root==null)
			root = newNode;
		else
		{
			Node current = root;
			Node parent;
			while(true)
			{
				parent = current;
				if(id < current.item)
				{
					current = current.leftChild;
					if(current == null)
					{
						parent.leftChild = newNode;
						return;
					}
				} 
				else
				{
					current = current.rightChild;
					if(current == null) 
					{
						parent.rightChild = newNode;
						return;
					}
				} 
			} 
		} 
	} 
	public int maxDepth(Node Root)
	{
		if(Root == null)
		{
			return 0;
		}
		return 1+ Math.max(maxDepth(Root.leftChild),maxDepth(Root.rightChild));
	}
	public int minDepth(Node Root)
	{
		if(Root == null)
		{
			return 0;
		}
		return 1 + Math.min(minDepth(Root.leftChild), minDepth(Root.rightChild));
	}
	public boolean isBalanced(Node Root)
	{
		return (maxDepth(Root) - minDepth(Root) <= 1);
	}
	public void displayTree()
	{
		Stack globalStack = new Stack();
		globalStack.push(root);	
		int emptyLeaf = 32;
		boolean isRowEmpty = false;
		System.out.println("****......................................................****");
		while(isRowEmpty==false)
		{

			Stack localStack = new Stack();
			isRowEmpty = true;
			for(int j=0; j<emptyLeaf; j++)
				System.out.print(' ');
			while(globalStack.isEmpty()==false)
			{
				Node temp = globalStack.pop();
				if(temp != null)
				{
					System.out.print(temp.item);
					localStack.push(temp.leftChild);
					localStack.push(temp.rightChild);
					if(temp.leftChild != null ||temp.rightChild != null)
						isRowEmpty = false;
				}
				else
				{
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				for(int j=0; j<emptyLeaf*2-2; j++)
					System.out.print(' ');
			}
			System.out.println();
			emptyLeaf /= 2;
			while(localStack.isEmpty()==false)
				globalStack.push( localStack.pop() );
		}
	System.out.println("****......................................................****");
	} 
} 
class TreeBalancedCheck
{

	public static void main(String[] args) throws IOException
	{
		int value;
		Tree theTree = new Tree();
		theTree.insert(42);
		theTree.insert(25);
		theTree.insert(65);
		theTree.insert(12);
		theTree.insert(37);
		theTree.insert(13);
		theTree.insert(30);
		theTree.insert(43);
		theTree.insert(87);
		theTree.insert(99);
		theTree.insert(9);
		theTree.insert(120);

		System.out.println("Displaying the tree");
		theTree.displayTree();

		if(theTree.isBalanced(theTree.returnRoot()))
		{
			System.out.println("The tree is balanced");
		}
		else
		{
			System.out.println("The tree is NOT balanced");
		}
	} 
} 

OUTPUT:

/Tree$ java TreeBalancedCheck 
Displaying the tree
****......................................................****
                                42                                                              
                25                              65                              
        12              37              43              87              
    9      13      30      --      --      --      --      99      
****......................................................****
The tree is balanced

Inserting 120 into the tree

:~/Tree$ java TreeBalancedCheck 
Displaying the tree
****......................................................****
                                42                                                              
                25                              65                              
        12              37              43              87              
    9      13      30      --      --      --      --      99      
  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  120  
****......................................................****
The tree is NOT balanced

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: