Convert a Ternary Tree to a Doubly Linked List

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:

 

Download   Run Code

Output:

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

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

avatar
  Subscribe  
Notify of