Introduction
A 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:
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm
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).
Also read - Merge sort in linked list