{"id":5944,"date":"2022-07-13T06:41:36","date_gmt":"2022-07-13T06:41:36","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5944"},"modified":"2022-12-14T10:43:15","modified_gmt":"2022-12-14T10:43:15","slug":"convert-a-given-binary-tree-to-circular-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/convert-a-given-binary-tree-to-circular-doubly-linked-list\/","title":{"rendered":"Convert a given Binary Tree To Circular Doubly Linked List"},"content":{"rendered":"

![](https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645007594981-Article_164.png)<\/p>\n

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\u2019s discuss our topic \u201cbinary tree to circular doubly linked list\u201d.<\/p>\n

## How To Convert Binary Tree To Circular Doubly Linked List
\nIn this problem, we are given a ternary tree, and we have to convert it to a doubly linked list.<\/p>\n

Let\u2019s try to understand the problem statement with the help of examples.<\/p>\n

**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.<\/p>\n

Let\u2019s assume that the given ternary tree is:<\/p>\n

\"\"<\/p>\n

\t– According to the problem statement, we need to convert this given ternary tree to a doubly linked list.
\n \t– After converting the given tree to doubly linked list, our doubly linked list will look like:<\/p>\n

\"\"<\/p>\n

Taking another example, if the given ternary tree is:<\/p>\n

\"\"<\/p>\n

\t– Then, in this case, after conversion, our doubly linked list will be:<\/p>\n

\"\"<\/p>\n

Now, I think from the above examples, the problem statement is clear. Let\u2019s see how we can approach it.<\/p>\n

Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n

\t– If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.<\/p>\n

Before moving on further, let\u2019s see some helpful observations, which will help us to approach this problem.<\/p>\n

**Helpful Observations To Convert Binary Tree To Circular Doubly Linked List**
\nLet\u2019s compare the relative position of nodes in the binary tree and doubly linked list.<\/p>\n

\"\"<\/p>\n

– 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.
\n – In the resultant doubly linked list, node 4 will occur before nodes 9, 5, and 1 as they are children’s of node 4.
\n – Similarly, node 6 will occur before nodes 2, 7, and 10 as they are the children’s of node 6.<\/p>\n

Hence, it is clear from above observations that every node should be inserted first in the doubly linked list, followed by its children’s.<\/p>\n

– 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.
\n – 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.<\/p>\n

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.<\/p>\n

In this way, our doubly linked list will be formed.<\/p>\n

## Approach To Convert Binary Tree To Circular Doubly Linked List
\nWhile creating a Doubly Linked List from a ternary tree, the Doubly Linked List must follow the following properties:<\/p>\n

– The left pointer<\/strong> of a node in ternary tree will act a prev<\/strong> pointer in the Doubly Linked List.
\n – The right pointer<\/strong> of a node in ternary tree will act a next<\/strong> pointer in the Doubly Linked List.
\n – The middle pointer<\/strong> of a ternary tree node will point to null.<\/p>\n

To create a desired Doubly Linked List from the given Ternary tree:<\/p>\n

– 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.<\/p>\n

In preorder traversal<\/strong>, 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.<\/p>\n

## Algorithm To Convert Binary Tree To Circular Doubly Linked List<\/p>\n

– Create head<\/strong> and tail<\/strong> of the linked list (head<\/strong> will be the starting point of the Doubly Linked List, and tail<\/strong> will store the last node of the Doubly Linked List).
\n – Perform a preorder traversal on the given tree.
\n – 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:<\/p>\n

– First, the tail.right<\/strong> will point to node<\/strong> to be inserted (tail.right = node)<\/strong>.
\n – Then node.left<\/strong> will point to tail<\/strong> (node.left = tail)<\/strong>.<\/p>\n

– Finally, output the desired Doubly Linked List.<\/p>\n

### Dry Run To Convert Binary Tree To Circular Doubly Linked List
\n\"\"
\n\"\"
\n\"\"
\n\"\"
\n\"\"<\/p>\n

## Code Implementation To Convert Binary Tree To Circular Doubly Linked List
\n\t\t\t\t\t\t