Posted on by Kalkicode

# Convert binary tree to circular doubly linked list

The problem involves converting a binary tree into a circular doubly linked list. In a circular doubly linked list, each node has pointers to both its previous and next nodes, and the last node's next pointer points back to the first node, creating a loop.

## Problem Statement

Given a binary tree, the task is to convert it into a circular doubly linked list such that the nodes are linked in an order similar to an in-order traversal of the binary tree.

## Example

Consider the following binary tree:

``````
-1
/   \
2     8
/ \   / \
3  -3 6   5
/   \   \
-7     4  -6
/     / \
9     1  -2
/
7``````

After converting the binary tree to a circular doubly linked list, the list will be: 3 <-> 2 <-> 9 <-> -7 <-> -3 <-> -1 <-> 6 <-> 7 <-> 1 <-> 4 <-> -2 <-> 8 <-> 5 <-> -6.

## Idea to Solve the Problem

To convert a binary tree into a circular doubly linked list, we need to follow these steps:

1. Traverse the binary tree in an in-order fashion.
2. For each node, set its left child's `right` pointer to the current node and the current node's `left` pointer to its left child.
3. Update the `root` of the circular doubly linked list.
4. Connect the last node's `right` pointer to the `root` and the `root`'s `left` pointer to the last node to complete the circular structure.

## Pseudocode

Here's the pseudocode to convert a binary tree into a circular doubly linked list:

``````function changeLink(node, l, r):
if node is not NULL:
// Visit left subtree with left and right node
// Visit right subtree with left and right node
if node.left is NULL:
node.left = l
if l is not NULL:
l.right = node
if node.right is NULL:
node.right = r
if r is not NULL:
r.left = node

function convertToCll():
if root is NULL:
return
temp = root
while temp.left is not NULL:
temp = temp.left
root = temp
while temp.right is not NULL:
temp = temp.right
temp.right = root
root.left = temp``````

## Algorithm Explanation

1. Traverse the binary tree in an in-order fashion and perform the link changes during traversal.
2. For each node, set its left child's `right` pointer to the current node and the current node's `left` pointer to its left child.
3. Update the `root` of the circular doubly linked list to the leftmost node of the binary tree.
4. Connect the last node's `right` pointer to the `root` and the `root`'s `left` pointer to the last node to complete the circular structure.

## Time Complexity

The time complexity of converting a binary tree into a circular doubly linked list is O(n), where n is the number of nodes in the binary tree. This is because we traverse all nodes in the binary tree once during the conversion process.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post