Convert a given Binary Tree to Doubly Linked List

Ishita Chawla
Last Updated: Aug 2, 2022

Introduction

linked list is a linear data structure where elements are not stored contiguously but randomly. They are instrumental in implementing stacks and queues, graphs, performing arithmetic operations on large integers, and representing sparse matrices. On the other hand, a binary tree is a tree in which each node has at the most 2 children. 

These two are significant topics and are often a part of various technical interviews. 

This blog will discuss one such problem involving a linked list and binary tree, Convert a given binary tree to a doubly-linked list.

Example

Consider the following binary tree:

The doubly-linked list for this binary tree is given by:

Let us see the different techniques that can be used to solve this problem:

Using Inorder Traversal

Algorithm

  • Perform inorder traversal on the given binary tree.
  • For every node that is encountered, insert it at the beginning of the doubly linked list.
  • The linked list is then reversed to maintain the same order of the nodes as in the inorder traversal.

Implementation

Program

// C++ program to convert a given binary tree to a doubly-linked list using inorder traversal.
#include <iostream>
using namespace std;

// Creating a node to store the binary tree.
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = NULL;
    }
};

// Function to print the doubly linked list.
void printDLL(Node *head)
{
    Node *curr = head;
    while (curr != NULL)
    {
        cout << curr->data << " ";
        curr = curr->right;
    }
}

// Helper function to convert a given binary tree to a doubly linked list using normal inorder traversal.
void convert(Node *root, Node *&head)
{
    // If the tree is empty.
    if (root == NULL)
    {
        return;
    }

    // Converting the left tree recursively.
    convert(root->left, head);
    root->left = NULL;

    // Storing the right child.
    Node *right = root->right;

    // Inserting the current node at the beginning of a doubly linked list.
    root->right = head;
    if (head != NULL)
    {
        head->left = root;
    }

    head = root;

    // Converting the right subtree recursively.
    convert(right, head);
}

// To reverse the doubly linked list.
void reverse(Node *&head)
{
    Node *prev = NULL;
    Node *current = head;

    while (current)
    {
        swap(current->left, current->right);
        prev = current;
        current = current->left;
    }

    if (prev != NULL)
    {
        head = prev;
    }
}

// Function to convert a given binary tree to a doubly linked list.
void convert(Node *root)
{
    // Assigning 'NULL' value to the 'HEAD' node.
    Node *head = NULL;

    // Convert this binary tree into a doubly linked list.
    convert(root, head);

    // Reversing the linked list.
    reverse(head);

    // Print the list.
    printDLL(head);
}

int main()
{
    // Inserting values in the binary tree.
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // Calling the function and printing the doubly linked list.
    cout << "The doubly linked list is given by: ";
    convert(root);

    return 0;
}


Output

The doubly linked list is given by:

4 2 5 1 6 3 7

Time Complexity

The time complexity is O(N), where N is the total number of nodes in the binary tree.

Since we are traversing the entire binary tree having N nodes, only once, the time complexity is given by O(N).

Space Complexity

The space complexity is O(N), where N is the height of the binary tree.

Since the recursive function is called, again and again, it will occupy a stack of size equal to the height of the tree, in the memory. For a skew tree, the height will be N, leading space complexity to O(N).

Using Reverse Inorder Traversal

This problem can also be solved using a single step as well. The algorithm has been explained below:

Algorithm

  • We will use reverse inorder traversal instead of using normal inorder traversal.
  • We will process the right subtree first and then the left subtree.
  • For every node that is encountered, insert it at the beginning of the doubly linked list.
  • The nodes will follow the same order as in the inorder traversal.

Implementation

Program

// C++ program to convert a given binary tree to a doubly linked list using reverse inorder traversal.
#include <iostream>
using namespace std;

// Creating a node to store the binary tree.
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = NULL;
    }
};

// Function to print the doubly linked list.
void printDLL(Node *&head)
{
    Node *curr = head;
    while (curr != NULL)
    {
        cout << curr->data << " ";
        curr = curr->right;
    }
}

// Helper function to convert a given binary tree to a doubly linked list using reverse inorder traversal.
void convert(Node *root, Node *&head)
{
    // If the tree is empty.
    if (root == NULL)
    {
        return;
    }

    // Converting the right tree recursively.
    convert(root->right, head);

    // Inserting the current node at the beginning of a doubly linked list.
    root->right = head;

    if (head != NULL)
    {
        head->left = root;
    }

    head = root;

    // Converting the left subtree recursively.
    convert(root->left, head);
}

// Function to convert a given binary tree to a doubly linked list.
void convert(Node *root)
{
    // Assigning ‘NULL’ value to the ‘HEAD’ node.
    Node *head = NULL;

    // Convert this binary tree into a doubly linked list.
    convert(root, head);

    // Print the list.
    printDLL(head);
}

int main()
{
    // Inserting values in the binary tree.
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // Calling the function and printing the doubly linked list.
    cout << "The doubly linked list is given by: ";
    convert(root);

    return 0;
}


Output

The doubly linked list is given by:

4 2 5 1 6 3 7

Time Complexity

The time complexity is O(N), where N is the total number of nodes in the binary tree.

Since we are traversing the entire binary tree having N nodes, only once, the time complexity is given by O(N).

Space Complexity

The space complexity is O(N), where N is the height of the binary tree.

Since the recursive function is called, again and again, it will occupy a stack of size equal to the height of the tree, in the memory. For a skew tree, the height will be N, leading space complexity to O(N).

Keeping track of the previous node- Inorder Traversal

This approach is the simplest of all the techniques that we have discussed above.

The algorithm has been explained below:

Algorithm

  • Perform inorder traversal on the given binary tree.
  • For every node that is encountered, insert it at the beginning of the doubly linked list.
  • Keep track of the previously processed node, say PREV.
  • For every node visited, set its left child to PREV and the previous node’s right child to the current node.

Implementation

Program

// C++ program to convert a given binary tree to a doubly linked list keeping track of the previous node in inorder traversal.
#include <iostream>
using namespace std;

// Creating a node to store the binary tree.
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = NULL;
    }
};

// Function to print the doubly linked list.
void printDLL(Node *&head)
{
    Node *curr = head;
    while (curr != NULL)
    {
        cout << curr->data << " ";
        curr = curr->right;
    }
}

// Helper function to convert a given binary tree to a doubly linked list.
// root --> current node.
// head --> head of the doubly linked list .
// prev --> previously processed node.
void convert(Node *curr, Node *&head, Node *&prev)
{
    // If the tree is empty.
    if (curr == NULL)
    {
        return;
    }

    // Converting the left tree recursively.
    convert(curr->left, head, prev);

    // Changing the pointers accordingly.
    if (prev != NULL)
    {
        // The current node's left child is equated with prev.
        curr->left = prev;

        // The right child of previous node is equated with 'curr'.
        prev->right = curr;
    }

    // If prev is null, update the head of the doubly linked list.
    else
    {
        head = curr;
    }

    
    // The previous pointer is updated to the current node after the current node is visited.
    prev = curr;

    // Converting the right subtree recursively.
    convert(curr->right, head, prev);
}

// Function to convert a given binary tree to a doubly linked list.
void convert(Node *root)
{
    // To keep track of the previously processed node.
    Node *prev = NULL;

    // Convert the above binary tree into a doubly linked list.
    convert(root, root, prev);

    // Root becomes the head of the doubly linked list.

    // Print the list.
    printDLL(root);
}

int main()
{
    // Inserting values in the binary tree.
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // Calling the function and printing the doubly linked list.
    cout << "The doubly linked list is given by: ";
    convert(root);

    return 0;
}


Output

The doubly linked list is given by:

4 2 5 1 6 3 7

Time Complexity

The time complexity is O(N), where N is the total number of nodes in the binary tree.

Since we are traversing the entire binary tree having N nodes, only once, the time complexity is given by O(N).

Space Complexity

The space complexity is O(N), where N is the height of the binary tree.

Since the recursive function is called, again and again, it will occupy a stack of size equal to the height of the tree, in the memory. For a skew tree, the height will be N, leading space complexity to O(N).

Key Takeaways

So, this blog discussed how to convert a given binary tree to a doubly-linked list using 3 different approaches. To learn more on topics like Linked ListGraphsTrees, head over right now to CodeStudio to practice problems on topics like and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes