Create a Doubly Linked List from the given Ternary Tree

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

Problem Statement

In this problem, we are given a ternary tree, and we have to convert it to a doubly linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Note: A ternary tree is very much similar to a binary tree, but instead of having two children, it has three children left, middle, and right.

Let’s assume that the given ternary tree is:

  • According to the problem statement, we need to convert this given ternary tree to a doubly linked list.
  • After converting the given tree to doubly linked list, our doubly linked list will look like:

Taking another example, if the given ternary tree is:

  • Then, in this case, after conversion, our doubly linked list will be:

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Before moving on further, let’s see some helpful observations, which will help us to approach this problem.

Helpful Observations

Let’s compare the relative position of nodes in the binary tree and doubly linked list.

  • Node 15 is the root node, so it occurs first in the doubly linked list. It is not part of any subtree rooted at some other node, i.e., it is not a child of any other node.
  • In the resultant doubly linked list, node 4 will occur before nodes 9, 5, and 1 as they are children's of node 4.
  • Similarly, node 6 will occur before nodes 2, 7, and 10 as they are the children's of node 6.

Hence, it is clear from above observations that every node should be inserted first in the doubly linked list, followed by its children's.

  • If we consider the children's of node 4, we observe that node 9 is before node 5 and node 5 is before node 1 in the doubly linked list.
  • If we consider the children's of node 6, we observe that node 2 is before node 7 and node 7 is before node 10 in the doubly linked list.

Hence, it is clear from above observations that from children's, the left child will be inserted first, followed by the mid-child and at last the right child.

In this way, our doubly linked list will be formed.

Approach

While creating a Doubly Linked List from a ternary tree, the Doubly Linked List must follow the following properties:

  • The left pointer of a node in ternary tree will act a prev pointer in the Doubly Linked List.
  • The right pointer of a node in ternary tree will act a next pointer in the Doubly Linked List.
  • The middle pointer of a ternary tree node will point to null.

To create a desired Doubly Linked List from the given Ternary tree:

  • We need to traverse the given tree using preorder traversal and insert the nodes in our Doubly Linked List following the preorder traversal of the tree.

In preorder traversal, the root is visited first, followed by its left child and then right child. So, we will add the node in our doubly linked list as soon as it is visited while doing preorder traversal on the given ternary tree.

Algorithm

  • Create head and tail of the linked list (head will be the starting point of the Doubly Linked List, and tail will store the last node of the Doubly Linked List).

  • Perform a preorder traversal on the given tree.

  • If the node is not present already in our linked list, then insert the node at the tail of the linked list. To insert a node to the list, we will use tail pointer. Suppose we have to add a node to the list, then:

    • First, the tail.right will point to node to be inserted (tail.right = node).
    • Then node.left will point to tail (node.left = tail).
  • Finally, output the desired Doubly Linked List.

Dry Run





Code Implementation

public class Prepbytes {
    static class treeNode {
         int data;
         treeNode left, middle, right;

         public treeNode(int data) {
             this.data = data;
             left = middle = right = null;
         }
     }
     static treeNode tail;

     public static void push(treeNode node) {
         tail.right = node;

         node.left = tail;

         node.middle = node.right = null;
         tail = node;
     }

     /* This is a recursive method to perform preorder traversal on the ternary tree. */
     public static void preorderRec(treeNode node, treeNode head) {
         if (node == null)
             return;
         treeNode left = node.left;
         treeNode middle = node.middle;
         treeNode right = node.right;
         if (tail != node) {
             push(node);
         }
         preorderRec(left, head);
         preorderRec(middle, head);
         preorderRec(right, head);
     }

     /* This method is used to start the preorder traversal on the ternary tree. */
     public static treeNode startPreorderTraversal(treeNode root) {
         treeNode head = root;
         tail = root;
         preorderRec(root, head);
         return head;
     }

     /* This method is used to print the final doubly linked list once all the nodes from the ternary tree have been added to it. */
     public static void printList(treeNode head) {
         while (head != null) {
             if (head.right != null) {
                 System.out.print(head.data + " ");
             } else {
                 System.out.print(head.data);
             }
             head = head.right;
         }

     }

     public static void main(String args[]) {
         treeNode root = new treeNode(15);
         root.left = new treeNode(4);
         root.middle = new treeNode(6);
         root.right = new treeNode(8);
         root.left.left = new treeNode(9);
         root.left.middle = new treeNode(5);
         root.left.right = new treeNode(1);
         root.middle.left = new treeNode(2);
         root.middle.middle = new treeNode(7);
         root.middle.right = new treeNode(10);
         treeNode head = startPreorderTraversal(root);
         System.out.println("Converted Doubly linked list");
         printList(head);
     }
}

Output

Converted Doubly linked list
15 4 9 5 1 6 2 7 10 8

Time Complexity: O(n), where n is the total number of nodes in the given tree. We are traversing the tree which takes linear time.

So, in this blog, we have tried to explain how you can create a doubly linked list from a ternary tree. This is one of the good problems that helps you strengthen your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post Convert a given Binary Tree To Doubly Linked List | Set 3
Next post Merge two sorted linked lists (in-place)

Leave a Reply

Your email address will not be published. Required fields are marked *