Convert a binary tree to a singly linked list

Why would anyone convert a binary tree to a linked list?

Interviewer asking this question expects your understanding of Binary Tree traversals to be top notch. The key here is you parse the nodes through in-order traversal and move them to the right side of the tree.
The image below shows what I said and the code will do this recursively

binart_search_tree 

Resultant tree looks like this

tree_to_linked_list

 

Now lets take a look at the code needed to achieve this. We will continue using the TreeNode class used in previous examples

Method used to do this is below

public static void flatten(TreeNode node){
	if (node==null){
		return ;
	}
	TreeNode leftTemp=node.left;
	TreeNode rightTemp=node.right;
	node.left=null; // since we are moving everything to right side of the tree
	flatten(leftTemp); // do this for left tree. Move it to the right side
	flatten(rightTemp); // similarly for the left children of the right sub tree
	node.right=leftTemp; 
	TreeNode currentNode=node;
	while(currentNode.right!=null){
		currentNode=currentNode.right;
	}
	currentNode.right=rightTemp;
}

public static void main(String[] args) {
	TreeNode root=new TreeNode(8);
	TreeNode.insert(root, new TreeNode(3));
	TreeNode.insert(root, new TreeNode(10));
	TreeNode.insert(root, new TreeNode(1));
	TreeNode.insert(root, new TreeNode(6));
	TreeNode.insert(root, new TreeNode(4));
	TreeNode.insert(root, new TreeNode(14));
	TreeNode.insert(root, new TreeNode(7));
	TreeNode.insert(root, new TreeNode(13));
	TreeNode.flatten(root);
	StringBuffer inorderbuf=new StringBuffer();
	TreeNode.getInorder(root, inorderbuf);
	System.out.println(inorderbuf);
}

Output of the program

8 3 1 6 4 7 10 14 13

 

Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself