CC-20 : Convert Binary Search Tree to Heap.

Description:

Given Binary Tree as input, convert the same into a Heap.

Test cases and expected outputs:

Input Parameters	Expected outputs
	BST to Heap : 26,30,33,42,46,51,61

Pseudocode:

Call method ConvertBSTToHeap() with root node of Binary Search Tree to convert it to Heap. Then call postOrderRecursive() with root node and ArrayList to get the output Heap structure.

Method ConvertBSTToHeap (BinTreeNode root):

Initialize ArrayList named al.

Call method inOrderRecursive() with root and al as arguments.

Initialize idx= {-1}.

Call InOrderToMaxHeap() with root, al and idx as arguments.

Method inOrderRecursive(parentNode, ArrayList):

If parentNode is null, return.

Call inOrderRecursive() with parent node’s left child as parameter.

Add parent node’s node data to In-order traversal ArrayList.

Call inOrderRecursive() with parent node’s right child as parameter.

Method InOrderToMaxHeap(parentNode, ArrayList, Int):

Recursively call InOrderToMaxHeap() with parentNode.leftChild, al and idx as arguments.

Recursively call InOrderToMaxHeap() with parentNode.rightChild, al and idx as arguments. parentNode.setNodeData(al.get(++idx[0])).

Method postOrderRecursive(parentNode, ArrayList):

If parentNode is null, return.

Call postOrderRecursive() with parent node’s left child as parameter.

Call postOrderRecursive() with parent node’s right child as parameter.

Add parent node’s node data to Post-order traversal ArrayList.

Code:

public class HeapConvertBSTToHeap {
 
public void inOrderRecursive(BinTreeNode parent, ArrayList<Integer> al){
	if (parent==null) {return;}
	inOrderRecursive(parent.getLeftChild(),al);
	al.add(parent.getNodeData());
	inOrderRecursive(parent.getRightChild(),al);
}

public void InOrderToMaxHeap(BinTreeNode parent, ArrayList<Integer> al, int[] idx) {
	if (parent==null) {return;}
	InOrderToMaxHeap(parent.getLeftChild(), al, idx);
	InOrderToMaxHeap(parent.getRightChild(), al, idx);
	parent.setNodeData(al.get(++idx[0]));
}

public void ConvertBSTToHeap(BinTreeNode root) {
	ArrayList<Integer> al=new ArrayList<Integer>();
	inOrderRecursive(root,al);
	int[] idx= {-1};
	InOrderToMaxHeap(root,al, idx);	
}

public void postOrderRecursive(BinTreeNode parent, ArrayList<Integer> al ) throws Exception{
	if (parent==null) {return;}
	postOrderRecursive(parent.getLeftChild(), al);
	postOrderRecursive(parent.getRightChild(), al);
	al.add(parent.getNodeData());
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;

public class HeapConvertBSTToHeap {
 
public void inOrderRecursive(BinTreeNode parent, ArrayList<Integer> al){
	if (parent==null) {return;}
	inOrderRecursive(parent.getLeftChild(),al);
	al.add(parent.getNodeData());
	inOrderRecursive(parent.getRightChild(),al);
}

public void InOrderToMaxHeap(BinTreeNode parent, ArrayList<Integer> al, int[] idx) {
	if (parent==null) {return;}
	InOrderToMaxHeap(parent.getLeftChild(), al, idx);
	InOrderToMaxHeap(parent.getRightChild(), al, idx);
	parent.setNodeData(al.get(++idx[0]));
}

public void ConvertBSTToHeap(BinTreeNode root) {
	ArrayList<Integer> al=new ArrayList<Integer>();
	inOrderRecursive(root,al);
	int[] idx= {-1};
	InOrderToMaxHeap(root,al, idx);	
}

public void postOrderRecursive(BinTreeNode parent, ArrayList<Integer> al ) throws Exception{
	if (parent==null) {return;}
	postOrderRecursive(parent.getLeftChild(), al);
	postOrderRecursive(parent.getRightChild(), al);
	al.add(parent.getNodeData());
}

public static void printArrayListSummary(ArrayList al, String label) throws Exception {
	if (al == null) { System.out.println("\n\n Input ArrayList was null !! \n"); return; }
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < al.size(); arrayIndex++) {
			System.out.print(al.get(arrayIndex));
			if (arrayIndex < al.size()-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}

public static void main(String[] args) {

	int[] retVal;
	try {
	HeapConvertBSTToHeap hp=new HeapConvertBSTToHeap();
	BinTreeNode root=hp.new BinTreeNode(42);
	//Left L1 Children
	root.setLeftChild(hp.new BinTreeNode(30));
	root.setRightChild(hp.new BinTreeNode(51));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(hp.new BinTreeNode(26));
	root.getLeftChild().setRightChild(hp.new BinTreeNode(33));
	
		
	//Right L2 Children
	root.getRightChild().setLeftChild(hp.new BinTreeNode(46));
	root.getRightChild().setRightChild(hp.new BinTreeNode(61));
	
	
	hp.ConvertBSTToHeap(root);
	ArrayList heap=new ArrayList();
	hp.postOrderRecursive(root, heap);
	printArrayListSummary(heap, "BST to Heap" );
	
	
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

public class BinTreeNode {
	private BinTreeNode leftNode=null;
private BinTreeNode rightNode=null;
private int nodeData=0;

public BinTreeNode(int data) {
	nodeData=data;
}	
public BinTreeNode getLeftChild() {
	return leftNode;
}
public void setLeftChild(BinTreeNode leftNode) {
	this.leftNode = leftNode;
}
public BinTreeNode getRightChild() {
	return rightNode;
}
public void setRightChild(BinTreeNode rightNode) {
	this.rightNode = rightNode;
}
public int getNodeData() {
	return nodeData;
}
public void setNodeData(int nodeData) {
	this.nodeData = nodeData;
}

}
}