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.

Example

Time complexity : O(n)

Algorithm

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;
    while(temp!=NULL)
        {
            if(temp->right!=NULL)
            cout<<temp->data<<" ->";
            else
            cout<<temp->data;
            
            temp=temp->right; //move to right node
        }
        //O(number of nodes)
    cout<<endl;
}
 
void Convert(Node* root, Node** head_ref)
{
    if (root == NULL)
    {
        return;
    }
    //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);
 
    display(&head);
 
    return 0;
}

 

Translate ยป