CC-18 : Serialize and Deserialize a Binary Tree.

Description:

In a mirror Binary Tree, all nodes have their left and right child nodes interchanged. Given a Binary Tree, find and return the mirror Binary Tree.

Test cases and expected outputs:

Input Parameters	Expected outputs
Serialize and de-serialize above tree.	Bfs traversal before Serialization: : 4,5,7,6,78,14,33,8,16,18,9 Bfs traversal after Serialization and deserialization: : 4,5,7,6,78,14,33,8,16,18,9

Pseudocode:

We will use StringBuilder variable named serial to hold the serialized Binary Tree.

We use character ‘*’ to separate left and right child of node in the variable serial.

We use character ‘#’ to indicate the current child of current node is null in the variable serial.

Method serializeBinTree(TreeNode root, StringBuilder serial):

If root node is null, append # and * to serial and return.

Else:

Append root node’s data and ‘*’ to serial.

Recursively call serializeBinTree() method with roots’ left child and serial as input parameters.

Recursively call serializeBinTree() method with roots’ right child and serial as input parameters.

Method deserializeBinTree(serial):

Tokenize serial on the token ‘*’ and store in variable named nodes or type StringTokenizer.

Return value returned by calling deserialize() with nodes as input parameter.

Method deserialize(nodes):

If nodes does not have any more token, return null.

Else:

Set variable data to next token of nodes.

If data is ‘#’ return null.

Else :

Create a new instance of BinTreeNode named node and set its node data member variable to data.

Set node’s left child to return value of recursive call to deserialize(nodes).

Set node’s right child to return value of recursive call to deserialize(nodes).

Return node.

Code:

public class BinTreeSerialize {	

private void serializeBinTree(BinTreeNode root, StringBuilder serial) {
	if (root==null) {serial.append("#").append("*"); return;}
	serial.append(root.getNodeData()).append("*");
	serializeBinTree(root.getLeftChild(), serial);
	serializeBinTree(root.getRightChild(), serial);	
}

private BinTreeNode deserialize(StringTokenizer nodes) {
	if (nodes.hasMoreTokens()==false) { return null;}
	String data=nodes.nextToken();
	if (data.equals("#")) {return null;}
	BinTreeNode node=new BinTreeNode(Integer.parseInt(data));
	node.setLeftChild(deserialize(nodes));
	node.setRightChild(deserialize(nodes));
	return node;
}

private BinTreeNode deserializeBinTree(StringBuilder serial) {
	StringTokenizer nodes=new StringTokenizer(serial.toString(),"*");
	return deserialize(nodes);
}

public ArrayList<Integer> bfsTraversal(BinTreeNode root) throws Exception{
	if (root==null) {return null;}
	ArrayList<Integer> bfs=new ArrayList<Integer>();
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	while (queue.size()!=0) {
		node=queue.poll();
		bfs.add(node.getNodeData());
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}	
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}
			
	}
	return bfs;
}
}

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.

Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BinTreeSerialize {	

private void serializeBinTree(BinTreeNode root, StringBuilder serial) {
	if (root==null) {serial.append("#").append("*"); return;}
	serial.append(root.getNodeData()).append("*");
	serializeBinTree(root.getLeftChild(), serial);
	serializeBinTree(root.getRightChild(), serial);	
}

private BinTreeNode deserialize(StringTokenizer nodes) {
	if (nodes.hasMoreTokens()==false) { return null;}
	String data=nodes.nextToken();
	if (data.equals("#")) {return null;}
	BinTreeNode node=new BinTreeNode(Integer.parseInt(data));
	node.setLeftChild(deserialize(nodes));
	node.setRightChild(deserialize(nodes));
	return node;
}

private BinTreeNode deserializeBinTree(StringBuilder serial) {
	StringTokenizer nodes=new StringTokenizer(serial.toString(),"*");
	return deserialize(nodes);
}

public ArrayList<Integer> bfsTraversal(BinTreeNode root) throws Exception{
	if (root==null) {return null;}
	ArrayList<Integer> bfs=new ArrayList<Integer>();
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	while (queue.size()!=0) {
		node=queue.poll();
		bfs.add(node.getNodeData());
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}	
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}
			
	}
	return bfs;
}

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) {
	/***********************
 	Test cases given below:
	 **********************/
	ArrayList<Integer>  retVal1;
	ArrayList<Integer>  retVal2;
	try {
	BinTreeSerialize ser=new BinTreeSerialize();
	BinTreeNode root=ser.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(ser.new BinTreeNode(5));
	root.setRightChild(ser.new BinTreeNode(7));	
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(ser.new BinTreeNode(6));
	root.getLeftChild().setRightChild(ser.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(ser.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(ser.new BinTreeNode(14));	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(ser.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(ser.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(ser.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(ser.new BinTreeNode(9));
	
	retVal1=ser.bfsTraversal(root);
	printArrayListSummary(retVal1, "Bfs traversal before Serialization: \n");
	
	StringBuilder serial=new StringBuilder();
	ser.serializeBinTree(root, serial);
	BinTreeNode newRoot=ser.deserializeBinTree(serial);
	retVal2=ser.bfsTraversal(newRoot);
	printArrayListSummary(retVal2, "Bfs traversal after Serialization and deserialization: \n");
	
	
	}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;
	}

}
	
}