Introduction
In this blog, we will learn to create a doubly linked list from a ternary tree. So, let’s get started with the creation of a doubly linked list from a ternary tree.
The ternary tree is a data structure with a maximum of three children per node. This is accomplished by traversing the ternary tree in the following order: root -> left child -> middle child ->, right child. To begin, traverse the root node and add it to the list. Then, add its right, middle, and left subtrees.
A Doubly Linked List is a type of linked list that allows easy traversal in both forward and backward directions.
Problem Statement
Write a program to create a Doubly Linked List from a Ternary Tree.
Example
The corresponding doubly linked list for the above ternary tree is:-
NULL <- 59 <-> 41 <-> 28 <-> 10 <-> 94 <-> 77 <-> 53 <-> 32 <-> 46 <-> 83 <-> 12 <-> 31 <-> 65 -> NULL
Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm
Approach
Let’s see the step-by-step method to create a doubly linked list from a ternary tree.
-
The root of the ternary tree will be represented by a root. The doubly linked list's head and tail are represented by the head and tail nodes.
-
We define a function to convert a ternary tree to a doubly-linked list.
-
Every node has three children which are represented by the left, center, and right nodes.
-
Check if the node isn't null, if not null it will be added to the doubly linked list.
-
Put that node at the end of the list if the list is not empty.
-
When a node has been successfully added to the list, run the function recursively to add the node's left, middle, and right children to the list.
-
Every node has three children which are represented by the left, center, and right nodes.
- Print the doubly linked list.
Implementation in C++
// C++ code to create doubly linked list from a ternary tree
#include <iostream>
using namespace std;
// Structure of a node of the ternary tree
struct Tree_Node
{
int val;
Tree_Node *left;
Tree_Node *middle;
Tree_Node *right;
};
// Creating a new node for tree
Tree_Node *makeTree_Node(int data)
{
Tree_Node *newTree_Node = new Tree_Node();
newTree_Node->val = data;
return newTree_Node;
}
Tree_Node *head = NULL, *tail = NULL;
// This function convert TERNARY TREE to DLL
void create_DLL_from_ternaryTree(Tree_Node *root)
{
// check if node is null or not
if (!root)
return;
// store address of left child
Tree_Node *left_subtree = root->left;
// store address of middle child
Tree_Node *middle_subtree = root->middle;
// store address of right child
Tree_Node *right_subtree = root->right;
if (head == NULL) // If list is empty
{
head = tail = root;
root->middle = head->left = tail->right = NULL;
}
// If list is not empty
else
{
tail->right = root;
root->left = tail;
root->middle = NULL;
tail = root;
tail->right = NULL;
}
// Recursively call left ,middle and right subtree one by one
create_DLL_from_ternaryTree(left_subtree);
create_DLL_from_ternaryTree(middle_subtree);
create_DLL_from_ternaryTree(right_subtree);
}
int main()
{
Tree_Node *root;
// Make a ternary tree by calling
// function makeTree_Node()
root = makeTree_Node(10);
root->left = makeTree_Node(12);
root->left->left = makeTree_Node(13);
root->left->middle = makeTree_Node(24);
root->left->right = makeTree_Node(54);
root->middle = makeTree_Node(25);
root->middle->left = makeTree_Node(26);
root->middle->middle = makeTree_Node(27);
root->middle->right = makeTree_Node(28);
root->right = makeTree_Node(29);
root->right->left = makeTree_Node(30);
root->right->middle = makeTree_Node(31);
root->right->right = makeTree_Node(32);
create_DLL_from_ternaryTree(root);
// function to display the linked list
Tree_Node *ptr = head;
if (head == NULL)
{
cout << "Your list is empty" << endl;
return NULL;
}
cout << "New converted doubly linked list is:" << endl
<< endl;
cout << "null";
while (ptr != NULL)
{
cout << " <-> " << ptr->val;
ptr = ptr->right;
}
cout << " <-> null" << endl;
return 0;
}
Output
The New converted doubly linked list is:
null <-> 10 <-> 12 <-> 13 <-> 24 <-> 54 <-> 25 <-> 26 <-> 27 <-> 28 <-> 29 <-> 30 <-> 31 <-> 32 <-> null
Complexity Analysis
Time Complexity
We are traversing the ternary tree only once, that's why the above approach has O(n) time complexity, where n is the total number of nodes in the ternary tree.
Space Complexity
The total space required for this approach is O(n) + O(h), where O(n) space is required to store the doubly linked list of n nodes and O(h) is the auxiliary space. Since the question demands the doubly linked list, hence we can ignore the space required to store it. So, the time complexity of this approach is O(h), where h is the tree's height.
Check out this problem - Largest BST In Binary Tree