Binary Tree To Double Linked List

In this blog, you will learn how to Parse a binary tree to double linked list.

Introduction

 

In this article we will discuss about a popular interview question, which is how would you convert a binary tree to a double linked list. Now, a binary tree is a hierachical graph data structure and that does makes binary search tree a part of the question, it just needs to be a binary tree. And a double linked list is a data structure where nodes that hold information are sequentially chained, each node holds a pointer to the next node in the chain.

 

 

Algorithm

 

We will choose the most naive approach for solving the problem. We'll do an in order traversal of the binary tree which ends up visiting the nodes in the order: 25 12 30 100, which is the order we want our double linked list to have. We'll keep track of the current node that we're looking at, and the previous node that we've visited. At each step, we'll make the current root node's left pointer point to the previous node, and we'll make the previous node's right pointer point to the current root node. We'll also cover one specific case where our first node becomes the previous node, and we have a head pointer for our linked list point to that node. Here is the C++ algorithm,

#include <iostream>
using namespace std;

struct Node {
    int Data;
    struct Node* Left;
    struct Node* Right;

    Node(int data) {
        this->Data = data;
        this->Left = NULL;
        this->Right = NULL;
    }
};
void PrintDoubleLinkedList(Node* head) {
    // for last nodes
    if(head == NULL) {
        cout << endl;
        return;
    }

    // print node
    cout << head->Data << " ";

    // recursively print
    PrintDoubleLinkedList(head->Right);
}
void ParseBinaryTree(Node* root, Node*& previous, Node*& header) {
    if(root == NULL) {
        return;
    }

    // for left nodes
    ParseBinaryTree(root->Left, previous, header);

    if(previous == NULL) {
        // Set the header & previous node for the first node
        header = root;
        previous = root;
    }
    else{
        // root node's left pointer point to the previous node
        root->Left = previous;

        // previous node's right pointer point to the root
        previous->Right = root;

        // update the previous node
        previous = root;
    }

    // for right nodes
    ParseBinaryTree(root->Right, previous, header);
}
int main() {
    // initailize a binary tree
    Node* root = new Node(100);
    root->Left = new Node(12);
    root->Left->Left = new Node(25);
    root->Left->Right = new Node(30);

    // intialize null header & prvious node nodes
    Node* header = NULL;
    Node* prevNode = NULL;

    // parse binary tree to linked list
    ParseBinaryTree(root, prevNode, header);

    cout << "DOUBLE LINKED LIST : ";
    // print the link list
    PrintDoubleLinkedList(header);

    return 0;
}

The time complexity is O(N), as we visit each node exactly once, and the space complexity is O(1), since we use no extra space.