Home » Interview Questions » LinkedList Interview Questions » Binary Tree to Doubly linked list

Binary Tree to Doubly linked list


Convert the given Binary Tree into a Doubly linked list in-place. The order of nodes should be same as in-order of the given binary tree. The left and right pointers of the tree node are to be used as previous and next.


Time complexity : O(n)


Traverse the tree in reverse in-order traversal. We are doing reverse in-order because, we insert nodes at the beginning, we need to process leaves in reverse order.

a. If root is null, return(Null DLL)

b. Recursively covert right subtree and insert node into DLL

c. Change left pointer of previous head to root. Change head of Doubly linked list equal to root. (we are inserting nodes in the beginning).

d. Recursively covert right subtree.

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node *right;
    Node *left;

void insertAtBeginning(struct Node **head, int X)
    struct Node * curr = new Node;
    curr->data = X;
    curr->left = NULL;
    curr->right = *head;
    if(*head != NULL)
    (*head)->left = curr;
    *head = curr;

void display(struct Node**head)
    struct Node*temp=*head;
            cout<<temp->data<<" ->";
            temp=temp->right; //move to right node
        //O(number of nodes)
void Convert(Node* root, Node** head_ref)
    if (root == NULL)
    //Right subtree
    Convert(root->right, head_ref);
    //Insert node
    root->right = *head_ref;
    if (*head_ref != NULL)
        (*head_ref)->left = root;
    *head_ref = root;
    //Left subtree
    Convert(root->left, head_ref);
// Utility function for allocating node for Binary
// Tree.
Node* newNode(int data)
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
//Main function
int main()
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);
    root->right->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    Node* head = NULL;
    Convert(root, &head);
    return 0;

READ  Merge Two Sorted Lists Leetcode


How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions