## 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

Resultant tree looks like this

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