Convert a given Binary Tree to Doubly Linked List | Set 3 | GeeksforGeeks

The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.

void BinaryTree2DoubleLinkedList(node *root, node **head)

{

    // Base case

    if (root == NULL) return;

 

    // Initialize previously visited node as NULL. This is

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

    // calls

    static node* prev = NULL;

 

    // Recursively convert left subtree

    BinaryTree2DoubleLinkedList(root->left, head);

 

    // 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, head);

}

Read full article from Convert a given Binary Tree to Doubly Linked List | Set 3 | GeeksforGeeks