Q:

Convert a given binary Tree to Doubly Linked List (DLL)

mahmoud2506
Save to bookmark
|
2022-05-08
|
  186 
0

Given a Binary tree and we have to convert it to a Doubly Linked List (DLL).

Binary tree to DLL conversion

 

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-08
need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

To solve the problem we can follow this algorithm:

  1. We start to convert the tree node to DLL from the rightmost tree node to the leftmost tree node.
  2. Every time we connect the right pointer of a node to the head of the DLL.
  3. Connect the left pointer of the DLL to that node.
  4. Make that node to the head of the linked list.
  5. Repeat the process from right to left most node of the tree.

C++ implementation:

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

struct node {
    int data;
    node* left;
    node* right;
};

//Create a new node
struct node* create_node(int x)
{
    struct node* temp = new node;
    temp->data = x;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

//convert a BST to a DLL
void BinarytoDll(node* root, node** head)
{
    if (root == NULL)
        return;
    BinarytoDll(root->right, head);
    root->right = *head;
    if (*head != NULL) {
        (*head)->left = root;
    }
    *head = root;
    BinarytoDll(root->left, head);
}

//Print the list
void print(node* head)
{
    struct node* temp = head;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->right;
    }
}

//print the tree in inorder traversal
void print_tree(node* root)
{
    if (root == NULL) {
        return;
    }
    print_tree(root->left);
    cout << root->data << " ";
    print_tree(root->right);
}

int main()
{
    struct node* root = create_node(5);
    root->left = create_node(6);
    root->right = create_node(7);
    root->left->left = create_node(8);
    root->left->right = create_node(1);
    root->right->right = create_node(0);
    cout << "Print Tree" << endl;
    print_tree(root);
    struct node* head = NULL;
    BinarytoDll(root, &head);
    cout << "\nDoubly Linked List" << endl;
    print(head);

    return 0;
}

Output

 
Print Tree
8 6 1 5 7 0
Doubly Linked List
8 6 1 5 7 0

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Data Structure programs using C and C++ (Linked List Programs)
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Modify contents of Linked List using C++ program... >>
<< Interchange the two adjacent nodes in a given circ...