BST_to_LL.txt

BST to LL
Send Feedback
Given a BST, convert it into a sorted linked list. You have to return the head of LL.
Input format:
The first and only line of input contains data of the nodes of the tree in level order form. The data of the nodes of the tree is separated by space. If any node does not have left or right child, take -1 in its place. Since -1 is used as an indication whether the left or right nodes exist, therefore, it will not be a part of the data of any node.   
Output Format:
The first and only line of output prints the elements of sorted linked list.
Constraints:
Time Limit: 1 second
Sample Input 1:
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
Sample Output 1:
2 5 6 7 8 10






import java.util.*;
import java.lang.*;
public class Solution {

	/*
	 * Binary Tree Node class
	 * 
	 * class BinaryTreeNode<T> { T data; BinaryTreeNode<T> left; BinaryTreeNode<T>
	 * right;
	 * 
	 * public BinaryTreeNode(T data) { this.data = data; } }
	 */

	/*
	 * LinkedList Node Class
	 *
	 * 
	 * class LinkedListNode<T> { T data; LinkedListNode<T> next;
	 * 
	 * public LinkedListNode(T data) { this.data = data; } }
	 */
    static List<Integer> data = new ArrayList<Integer>();
    
	public static void inOrder(BinaryTreeNode<Integer> root) {
		//Your code goes here
        if(root == null)
            return;
        
        inOrder(root.left);
        data.add(root.data);
        inOrder(root.right);
        
	}
 
	public static LinkedListNode<Integer> constructLinkedList(BinaryTreeNode<Integer> root) {
        	
        	if(root == null)
                return null;
        	
        	inOrder(root);
			LinkedListNode<Integer> head = new LinkedListNode<Integer>(data.get(0));
			LinkedListNode<Integer> temp = head;
        	
        	for(int i=1; i<data.size(); i++){
				LinkedListNode<Integer> tail = new LinkedListNode<Integer>(data.get(i));
                temp.next = tail;
                temp = temp.next;  
            }
        	temp.next = null;
        
        	return head;   	
        	
	}
}