Binary Tree to DLL Java

PROGRAM TO CONVERT A GIVEN BINARY TREE TO DOUBLY LINKED LIST

class Node

{

    int data;

    Node left, right;

  

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  

class BinaryTree

{

    Node root;

      

    // head --> Pointer to head node of created doubly linked list

    Node head;

      

    // Initialize previously visited node as NULL. This is

    // static so that the same value is accessible in all recursive

    // calls

    static Node prev = null;

  

    // A simple recursive function to convert a given Binary tree

    // to Doubly Linked List

    // root --> Root of Binary Tree

    void BinaryTree2DoubleLinkedList(Node root)

    {

        // Base case

        if (root == null)

            return;

  

        // Recursively convert left subtree

        BinaryTree2DoubleLinkedList(root.left);

  

        // Now convert this node

        if (prev == null)

            head = root;

        else

        {

            root.left = prev;

            prev.right = root;

        }

        prev = root;

  

        // Finally convert right subtree

        BinaryTree2DoubleLinkedList(root.right);

    }

  

    /* Function to print nodes in a given doubly linked list */

    void printList(Node node)

    {

        while (node != null)

        {

            System.out.print(node.data + " ");

            node = node.right;

        }

    }

  

    // Driver program to test above functions

    public static void main(String[] args)

    {

        // Let us create the tree as shown in above diagram

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

        tree.root.left = new Node(12);

        tree.root.right = new Node(15);

        tree.root.left.left = new Node(25);

        tree.root.left.right = new Node(30);

        tree.root.right.left = new Node(36);

  

        // convert to DLL

        tree.BinaryTree2DoubleLinkedList(tree.root);

          

        // Print the converted List

        tree.printList(tree.head);

  

    }

}




OUTPUT:

25 12 30 10 36 15

CREDITS: https://www.geeksforgeeks.org/convert-given-binary-tree-doubly-linked-list-set-3/