@@ -0,0 +1,2177 @@
+package com.interview.tree;%0A%0A/**%0A * Date 03/16/2015%0A * @author tusroy%0A * %0A * Given a binary tree(not BST) convert it into sorted linklist.%0A * e.g          10%0A *          11        15%0A *        8    9    16   13%0A *                           7%0A *                           %0A * should become 7-%3E8-%3E9-%3E10-%3E11-%3E13-%3E15-%3E16%0A * %0A * Solution%0A * Idea is that at every root, get the sorted linklist from left and right and merge them %0A * along with root and return left most element in this merged linklist to upper level call.%0A * %0A * Test cases%0A * 1) Null root%0A * 2) One node root%0A * 3) BST %0A * 4) Reverse BST%0A * 5) All on left side of root%0A * %0A * Reference%0A * http://www.careercup.com/question?id=6241652616200192%0A *%0A */%0Apublic class DegenerateBinaryTreeToSortedLL %7B%0A   %0A    public Node degenerate(Node root)%7B%0A        if(root == null)%7B%0A            return null;%0A        %7D%0A        %0A        Node left = root.left;%0A        Node right = root.right;%0A        root.left = null;%0A        root.right = null;%0A        left = degenerate(left);%0A        right = degenerate(right);%0A        left = merge(left, root);%0A        return merge(left, right);%0A    %7D%0A    %0A    private Node merge(Node root1, Node root2)%7B%0A        if(root1 == null)%7B%0A            return root2;%0A        %7D%0A        if(root2 == null)%7B%0A            return root1;%0A        %7D%0A        %0A        if(root1.data %3C= root2.data)%7B%0A            root1.right = merge(root1.right, root2);%0A            return root1;%0A        %7Delse%7B%0A            root2.right = merge(root1, root2.right);%0A            return root2;%0A        %7D%0A    %7D%0A    %0A    private void printList(Node root)%7B%0A        while(root != null)%7B%0A            System.out.print(root.data + %22 %22);%0A            root = root.right;%0A        %7D%0A    %7D%0A    %0A    public static void main(String args%5B%5D)%7B%0A        ConstructTreeFromInOrderPreOrder ctf = new ConstructTreeFromInOrderPreOrder();%0A        int inorder%5B%5D = %7B8, 11, 9, 10, 16, 15, 13, 7%7D;%0A        int preorder%5B%5D = %7B10, 11, 8, 9, 15, 16, 13, 7%7D;%0A        Node root = ctf.createTree(inorder, preorder);%0A        DegenerateBinaryTreeToSortedLL dbt = new DegenerateBinaryTreeToSortedLL();%0A        root = dbt.degenerate(root);%0A        dbt.printList(root);%0A    %7D%0A    %0A%7D%0A

Convert binary tree to sorted linklist