Write an efficient algorithm to convert a ternary tree into a doubly linked list. A ternary tree is a tree data structure in which each node has at most three child nodes distinguished as left, mid and right.

The conversion should be done in such a way that the left child pointer of a ternary tree node should act as a previous pointer for doubly linked list node, the right child pointer should act as a next pointer for doubly linked list node, and the mid child pointer should point to null. The conversion should be done by only exchanging ternary tree node pointers without allocating any extra memory for the nodes of doubly linked list.

Consider below ternary tree which shows order in which the nodes should be present in a doubly linked list.

1

/ | \

/ | \

/ | \

2 9 12

/ | \ / \ | \

3 6 8 10 11 13 16

| \ / \ |

4 7 14 15 17

\

5

**Output:** Doubly linked list

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> nullptr

As evident from above example, the root node of ternary tree is pushed before its children into the doubly linked list. This is recursively followed by every node in subtree rooted at its left child, mid child and right child, in that order.

The idea is perform reverse postorder traversal for a ternary tree. In reverse postorder traversal, before processing a node of ternary tree, its right child is processed first, followed by its mid and left child. After traversing all childrens of a ternary tree node, we insert the node in the front of the doubly linked list. The reverse postorder traversal is used to ensure the correct insertion order in doubly linked list.

Here’s a C++ program to demonstrate the idea:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <iostream> #include <string> #include <utility> using namespace std; // Data structure to store a ternary tree node struct Node { int data; Node *left, *mid, *right; }; // Function to create a new ternary tree node with given key Node* newNode(int data) { Node* node = new Node; node->data = data; node->left = node->mid = node->right = nullptr; return node; } // Insert a tree node at the front of the doubly linked list void push(Node* node, Node* &headRef) { // insert given node at the front of the doubly linked list headRef->left = node; node->right = headRef; // update left and mid child pointer to null node->left = node->mid = nullptr; // update head pointer to point to given node headRef = node; } // Convert a ternary tree into a doubly linked list using // reverse postorder traversal void TernaryTreeToDoublyList(Node* root, Node* &headRef) { // base case: an empty tree if (root == nullptr) return; // recur for right, mid and left child TernaryTreeToDoublyList(root->right, headRef); TernaryTreeToDoublyList(root->mid, headRef); TernaryTreeToDoublyList(root->left, headRef); // initialize head pointer of doubly linked list if (headRef == nullptr) { headRef = root; } else { // push current node in the front of the doubly linked list push(root, headRef); } } // Helper function to print a doubly linked list void printDoublyList(Node* ptr) { while (ptr) { cout << ptr->data << " -> "; ptr = ptr->right; } cout << "nullptr"; } // main function int main() { /* construct below ternary tree 1 / | \ / | \ / | \ 2 9 12 / | \ / \ | \ 3 6 8 10 11 13 16 | \ / \ | 4 7 14 15 17 \ 5 */ Node* root = newNode(1); root->left = newNode(2); root->mid = newNode(9); root->right = newNode(12); root->left->left = newNode(3); root->left->mid = newNode(6); root->left->right = newNode(8); root->mid->left = newNode(10); root->mid->right = newNode(11); root->right->mid = newNode(13); root->right->right = newNode(16); root->left->left->mid = newNode(4); root->left->left->right = newNode(5); root->left->mid->right = newNode(7); root->right->mid->left = newNode(14); root->right->mid->right = newNode(15); root->right->right->mid = newNode(17); Node* head = nullptr; TernaryTreeToDoublyList(root, head); printDoublyList(head); return 0; } |

`Output:`

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> nullptr

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply