# Create a Doubly Linked List from a Ternary Tree in C++

In this tutorial, we are going to learn how to create a doubly linked list from a ternary tree in C++. Here we will learn about the ternary tree, doubly linked list, and how to create a doubly linked list from a ternary tree. After that we will see the C++ program for the same.

## Ternary Tree

A ternary tree is a data structure in which each node has at most three children.
Ternary means composed of three parts. So, in a ternary tree, the parent node can have at most three child nodes, which are often called as the ‘left’, ‘middle’, and ‘right’ node, respectively. The structure of a node is defined as:-

```struct node{
int val;
struct node *left;
struct node *middle;
struct node *right;
};```

Here, the variables ‘left’ points to the left subtree, ‘middle’ points to the middle subtree, and ‘right’ points to the right subtree. The variable ‘val’ stores the value or data of a node. Let us see an example:-

1
/     |     \
/         |         \
6         10
/  |  \       /  |  \       /  |  \
3   4   5     7  8     11  12  13

A doubly-linked list is a data structure that contains sequentially linked records i.e. nodes. It is a variation of a singly linked list. In the doubly linked list we can move or traverse in both the direction forward as well as backward. The structure of a node is defined as:-

```struct node {
int val;
struct node* next;
struct node* prev;
};```

Here, the variable ‘next’ points to the next node, and the variable ‘prev’ points to the previous node. The variable ‘val’ stores the value or data of a node. Let us see an example:-

null<–>1<–>2<–>3<–>4<–>5<–>6<–>7<–>8<–>9<–>10<–>11<–>12<–>13<–>null

## Algorithm to create a doubly linked list from a ternary tree

We can create a doubly linked list from the ternary tree by using any of the following traversal:-

• Using pre-order traversal.
• Using in-order traversal.
• Or, using post-order traversal.

Here, we will create a doubly-linked list from the given ternary tree by storing the pre-order traversal of the given ternary tree. So, here are the steps to create a doubly linked list from a ternary tree:-

1. Create a ternary tree with any number of nodes.
3. Perform the pre-order traversal of the ternary tree.
4. While performing the pre-order traversal, append the current node in the doubly-linked list simultaneously.
5. At last, our doubly linked list is created from a ternary tree and it contains the pre-order traversal of the ternary tree.

## C++ program to create a doubly linked list from ternary tree

So, here is the C++ implementation of the above algorithm:-

```#include<bits/stdc++.h>
using namespace std;
//Structure of a node of the ternary tree

struct TreeNode
{
int val;
TreeNode *left;
TreeNode *middle;
TreeNode *right;
};

/*=====================================================
FUNCTION TO CONVERT TERNARY TREE TO DOUBLY LINKED LIST
=======================================================*/
void create_doubly_from_ternary(TreeNode *root)
{
// Check node is null or not.If it is null then return
if(!root)
return;

//storing the address of left child
TreeNode *left_subtree = root->left;
//storing the address of middle child
TreeNode *middle_subtree = root->middle;
//storing the address of right child
TreeNode *right_subtree = root->right;

if(head == NULL)             // If list is empty
{
// Make head and tail equal to root;
//& tail->right
root->middle = head->left = tail->right = NULL;
}

//If list is not empty
else {
//insert new node after tail
tail->right = root;
//And store tail address in root->left to maintain
root->left = tail;
root->middle = NULL;
//root will become new tail
tail = root;
//And tail->right should be null
tail->right = NULL;
}

//Recursively call left subtree
create_doubly_from_ternary(left_subtree);
//Recursively call middle subtree
create_doubly_from_ternary(middle_subtree);
//Recursively call right subtree
create_doubly_from_ternary(right_subtree);
}

/*============================================
FUNCTION TO DISPLAY THE DOUBLY LINKED LIST
=============================================*/
{
if(head == NULL)       //Checking for empty list
{
return;
}
cout<<"New converted doubly linked list is:"<<endl<<endl;
cout<<"null";
while(ptr != NULL)    //Terminate when ptr==NULL
{
cout<<" <-> "<<ptr->val;
ptr = ptr->right;   //Increment ptr to right
}
cout<<" <-> null"<<endl;
}

/*===========================================
FUNCTION TO CREATE NEW NODE FOR TERNARY TREE
============================================*/
TreeNode* makeTreeNode(int data)
{
TreeNode *newTreeNode = new TreeNode();
newTreeNode->val = data;
return newTreeNode;
}

/*======================================
MAIN FUNCTION
=======================================*/
int main()
{
TreeNode *root;
//Make a ternary tree by calling
//function makeTreeNode()
root = makeTreeNode(1);
root->left = makeTreeNode(2);
root->left->left = makeTreeNode(3);
root->left->middle = makeTreeNode(4);
root->left->right = makeTreeNode(5);
root->middle = makeTreeNode(6);
root->middle->left = makeTreeNode(7);
root->middle->middle = makeTreeNode(8);
root->middle->right = makeTreeNode(9);
root->right = makeTreeNode(10);
root->right->left = makeTreeNode(11);
root->right->middle = makeTreeNode(12);
root->right->right = makeTreeNode(13);

//Representation of input tree
//                  1
//            /     |     \
//        /         |         \
//       2          6         10
//    /  |  \    /  |  \    /  |  \
//   3   4   5  7   8  9   11  12  13

//Calling converting function that create doubly
create_doubly_from_ternary(root);

//Calling display function to print final
```New converted doubly linked list is: