Last Updated on December 14, 2022 by Prepbytes
In this article, we will deep dive and discuss how to convert the binary tree to circular doubly linked list. Converting a binary tree to circular doubly linked list will enhance your data structures topic like binary tree and linked list. Let’s discuss our topic “binary tree to circular doubly linked list”.
## How To Convert Binary Tree To Circular Doubly Linked List
In this problem, we are given a ternary tree, and we have to convert it to a doubly linked list.
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 To Convert Binary Tree To Circular Doubly Linked List**
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 To Convert Binary Tree To Circular Doubly Linked List
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 To Convert Binary Tree To Circular Doubly Linked List
– 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 To Convert Binary Tree To Circular Doubly Linked List
## Code Implementation To Convert Binary Tree To Circular Doubly Linked List
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 To Convert Binary Tree To Circular Doubly Linked List:** O(n), where n is the total number of nodes in the given tree. We are traversing the tree which takes linear time.
In this blog, we have discussed the best approach to convert binary tree to circular doubly linked list. If you want to conquer the data structures then you have to practice questions of data structures like linked list regularly. Our experts have planned and made the list of questions of linked list, you can checkout Prepbytes (Linked List) for solving more questions of linked list.
## FAQ
**1. How do you convert a binary tree to a doubly linked list?**
The binary tree is a tree data structure in which each node has at most two children nodes. This can be achieved by traversing the tree in the in-order manner, that is, left the child -> root ->right node. Traverse left subtree and convert it into the doubly linked list by adding nodes to the end of the list
**2. What is a circular doubly linked list?**
A Doubly Circular Linked List is a data structure that has properties of both Circular Linked List and Doubly Linked List. It is a list in which the last node of the list points to the start node, creating a loop.
**3. Which companies asked the conversion of binary trees into circular doubly linked lists?**
Amazon, Adobe, JP Morgan, Morgan Stanley, BNY Mellon in their recent interviews asked for the conversion of binary trees into circular doubly linked lists.