Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
Is a ternary tree the same as a binary tree?
3.2.
What is the real-life application of a ternary tree?
3.3.
Is it possible to make a doubly-linked list with just one pointer for each node?
3.4.
What is a circular link list?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Create a Doubly Linked List from a Ternary Tree

Author Prerna Tiwari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

  1. 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.
     
  2. We define a function to convert a ternary tree to a doubly-linked list.
    1. Every node has three children which are represented by the left, center, and right nodes.
       
    2. Check if the node isn't null, if not null it will be added to the doubly linked list.
       
    3. Put that node at the end of the list if the list is not empty.
       
    4. 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.
       
  3.   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;
}
You can also try this code with Online C++ Compiler
Run Code


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

Frequently Asked Questions

Is a ternary tree the same as a binary tree?

A ternary tree is a form of tree data structure in computer science that allows each node to have up to three derivative nodes. On the other hand, a binary tree can have one or two derived nodes for each node.

What is the real-life application of a ternary tree?

Ternary search trees can be used to hold all of the words in a dictionary. Once the word has been typed into an editor, it may be checked for correct spelling by running it through the ternary search tree in parallel.

Is it possible to make a doubly-linked list with just one pointer for each node?

Yes, we can make a doubly-linked list with just one pointer for each node by storing the XOR of the previous and next node's addresses.

What is a circular link list?

A circular linked list is a linked list in which the last node points to the first, forming a complete circle of nodes.

Conclusion

In this article, we have discussed how we can create a doubly linked list from a ternary tree. We started by introducing the ternary tree, doubly linked list, and the problem statement, we also discussed the implementation of the problem in C++ and finally concluded with time and space complexity.

We hope that this blog has helped you enhance your knowledge regarding creating a doubly-linked list from a ternary tree and if you would like to learn more, check out our other articles in our library Doubly Linked List.

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Live masterclass