Posted on by Kalkicode
Code Circular Linked List

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
        changeLink(node.left, l, node)
        // Visit right subtree with left and right node
        changeLink(node.right, node, r)
        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
    // Change node links
    changeLink(root, NULL, NULL)
    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.

Code Solution

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.

New Comment