BinaryTreeToLinkedList.java

package trees;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeToLinkedList {


    /*
     * Convert a binary tree to a doubly linked list such that the order of the doubly linked list is the same as an in-order traversal of the binary tree.
     * After conversion the left pointer of the node should be pointing to the previous node in the doubly linked list and the right pointer should be
     * pointing to the next node in the doubly linked list.
     *
     * Binary Node: 100, 50, 200, 25, 75, 125, 350
     * Its in-order traversal will be 25, 30, 50, 60, 75, 100, 125, 200, 350. So the output doubly linked list should look like so:
     * 25, 30, 50, 60, 75, 100, 125, 200, 350
     *
     * Runtime Complexity:
     * Linear, O(n)
     * Runtime complexity is based on the number of nodes in the tree.
     *
     * Memory Complexity:
     * Linear, O(h)
     *
     * Start with the root node and solve left and right sub-trees recursively
     * At each step, once left and right sub-trees have been processed:
     *      - fuse output of left subtree with root to make the intermediate result
     *      - fuse intermediate result (built in the previous step) with output from the right sub-tree to make the final result of the current recursive call
     *
     * */

    private static class Node {
        private int data;
        private Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }


    private Node root1;

    protected static Node concatenateLists(Node head1,
                                           Node head2) {

        if (head1 == null) {
            return head2;
        }

        if (head2 == null) {
            return head1;
        }

        // use left for previous.
        // use right for next.
        Node tail1 = head1.left;
        Node tail2 = head2.left;

        tail1.right = head2;
        head2.left = tail1;

        head1.left = tail2;
        tail2.right = head1;
        return head1;
    }


    protected static Node convertToLinkedList(Node root) {

        if (root == null) {
            return null;
        }

        Node list1 = convertToLinkedList(root.left);
        Node list2 = convertToLinkedList(root.right);

        root.left = root.right = root;
        Node result = concatenateLists(list1, root);
        result = concatenateLists(result, list2);

        return result;
    }
    

    static List<Integer> getList(Node head) {
        List<Integer> r = new ArrayList<Integer>();
        if (head == null) {
            return r;
        }

        Node temp = head;
        do {
            r.add(temp.data);
            temp = temp.right;
        } while (temp != head);

        return r;
    }
    

    public static void main(String[] args) {

        BinaryTreeToLinkedList binaryTreeToLinkedList = new BinaryTreeToLinkedList();
        binaryTreeToLinkedList.root1 = new Node(100);
        binaryTreeToLinkedList.root1.left = new Node(50);
        binaryTreeToLinkedList.root1.right = new Node(200);
        binaryTreeToLinkedList.root1.left.left = new Node(25);
        binaryTreeToLinkedList.root1.left.right = new Node(75);
        binaryTreeToLinkedList.root1.right.left = new Node(125);
        binaryTreeToLinkedList.root1.right.right = new Node(350);

        Node head = convertToLinkedList(binaryTreeToLinkedList.root1);
        List<Integer> result = getList(head);
        System.out.println(result);
    }
}