CC-19 : Convert Binary Tree to LinkedList.

Description:

Convert a Binary Tree to a Linked List. To do this, the right child link of Binary Tree will be used as nextNode link of Linked List. The left children of nodes will be added to Linked List as right children and left child link will be set as null. Given a Binary Tree, convert it to LinkedList using above described logic.

Test cases and expected outputs:

Input Parameters	Expected outputs
Convert above tree to a LinkedList.	Bfs traversal Orig Tree : 4,5,7,6,78,14,33,8,16,18,9 After converting to LinkedList Bfs traversal : 4,5,6,33,78,7,14,8,16,18,9

Pseudocode:

We will use PrevNode member variable to store a reference of previous node that was processed.

Method convertToLinkedList(TreeNode node):

If root node is null, return.

Else:

Recursively call convertToLinkedList() method with node’s right child as input parameter.

Recursively call convertToLinkedList() method with node’s left child as input parameter.

Set right child of node to PrevNode.

Set left child of node to null.

Set prevNode to node.

Code:

public class BinTreeToLinkedList{
	
private BinTreeNode prevNode=null;	

private void convertToLinkedList(BinTreeNode node) {
	if (node==null) {return;}
	convertToLinkedList(node.getRightChild());
	convertToLinkedList(node.getLeftChild());
	node.setRightChild(prevNode);
	node.setLeftChild(null);
	prevNode=node;
}
}

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;

public class BinTreeToLinkedList{
	
private BinTreeNode prevNode=null;	

private void convertToLinkedList(BinTreeNode node) {
	if (node==null) {return;}
	convertToLinkedList(node.getRightChild());
	convertToLinkedList(node.getLeftChild());
	node.setRightChild(prevNode);
	node.setLeftChild(null);
	prevNode=node;
}

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>  retVal;
	try {
	BinTreeToLinkedList ll=new BinTreeToLinkedList();
	BinTreeNode root=ll.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(ll.new BinTreeNode(5));
	root.setRightChild(ll.new BinTreeNode(7));	
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(ll.new BinTreeNode(6));
	root.getLeftChild().setRightChild(ll.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(ll.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(ll.new BinTreeNode(14));
	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(ll.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(ll.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(ll.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(ll.new BinTreeNode(9));
	
	retVal=ll.bfsTraversal(root);
	printArrayListSummary(retVal, "Bfs traversal");
	
	ll.convertToLinkedList(root);
	System.out.println("After converting to  LinkedList ");
	retVal=ll.bfsTraversal(root);
	printArrayListSummary(retVal, "Bfs traversal");	
	
	}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;
	}

}
	
}