Convert a given Binary Tree To Circular Doubly Linked List

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 binary tree, and we have to convert it to a circular doubly linked list.

Problem Statement Understanding

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

Let’s assume that the given binary tree is:

  • According to the problem statement, we need to convert this given binary tree to a circular doubly linked list.
  • After the conversion, our circular doubly linked list will look like this:
  • Taking another example, if the given binary tree is:

  • Then, in this case, our circular 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 to approach this problem in the next section.

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

    Helpful Observations

    To check the relative position of nodes in the binary tree and circular doubly linked list, let’s name every node.

    After naming the nodes in the binary tree, we can observe that:

    • The root node is A, with B as its left child and C as its right child.
    • B has D as its left child and E as its right child.
    • C has F as its left child and G as its right child.

    In the converted circular doubly linked list, we can observe that:

    • Node B has D as its previous node, which was its left child in the binary tree, and E as its next node, which was its right child in the binary tree.
    • Node C has F as its previous node, which was its left child in the binary tree, and G as its next node, which was its right child in the binary tree.

    So, from the above observations, you might think that we can just make the previous pointer of a node point to its left child and the next pointer point to its right child.

    • Yes, that is partially true because, if you see carefully, you can see that in the binary tree the node A has B as its left child, but in the converted doubly linked list its previous pointer is pointing to E not B.

    Another observation here is that all the nodes in the left subtree rooted at a node lie on the left side of the node in the list. Similarly, all the nodes in the right subtree rooted at a node lie on the right side of the node in the list.

    • We can achieve this using inorder traversal of the tree.

    Inorder traversal: In inorder traversal, first visit the left subtree, then the root, and then right subtree:

    If we do the inorder traversal of the above-given tree, we will get 7 2 8 0 9 3 10.

    On careful observation, you can see, the values are in the same order as in our output circular doubly linked list.

    So, the key takeaways are:

    • The left child can only be replaced with the previous node and the right child with the next node.
    • The nodes of the doubly linked list should follow the same order as the inorder traversal of the tree.

    Approach

    • We first convert the left subtree to a circular doubly linked list and then convert the right subtree to a circular doubly linked list.
    • Now the question arises, how do we convert the left subtree or the right subtree to a circular doubly linked list. And the answer is recursion.
    • A subtree follows all the properties of the parent tree. So this problem is similar to the original problem.
      • We treat the left child of the root as the new root and convert the subtree rooted at the left child(left child of the left child of the original root) of the new root(left child of the original root) and then convert the new root and then the subtree rooted at the right child of the new root.
      • We perform this operation recursively until the problem becomes trivial to solve. By trivial problem, I mean converting a binary tree that has at most three nodes, a root, left child, and right child. This problem can be solved easily as we just first append the left child to the list, then the root, and then the right child.
    • From the above observations, it is clear that the list will have nodes in the same order as the inorder traversal of the tree. So, we first concatenate the left list with the root and then concatenate the right list to it.
    • To concatenate two lists, we will perform the following steps:
      • Create a link from the last node of the first list to the first node of the second list and vice versa.
      • Create a link from the first node of the first list to the last node of the second list and vice versa.

    Algorithm

    To convert the given binary tree to a circular doubly linked list, we will do the preorder traversal of the binary tree.

    convertToCircularDLL(root)

    1) If the root is null, return null.
    2) Recursively convert left subtree to a circular doubly linked list (say left list).
    3) Recursively convert right subtree to a circular doubly linked list (say right list).
    4) Set root.left and root.right as root.
    5) Concatenate the left list with root.
    6) Concatenate the list we got after concatenating the left list and the root with the right list.
    7) Return the final concatenated list.

    Note: As you can see that earlier, we mentioned that our output list is equivalent to the inorder traversal of the given binary tree, but here in approach, we are using preorder traversal to generate the list. Actually, instead of preorder traversal, we can also use inorder traversal to generate the output list. In case of inorder traversal in function convertToCircularDLL(root), first, we will recursively convert the left subtree and will concatenate the left list with root, and then we will recursively convert the right subtree and will finally concatenate the right list with the concatenated output of left list and root and will return it.

    concatenateLists(left list, right list)

    1) If the left list is null, return the right list.
    2) If the right list is null, return the left list.
    3) Create a variable to store the last node of the left list.
    4) Create a variable to store the last node of the right list.
    5) Create a link from the last node of the left list to the first node of the right list and vice versa.
    6) Create a link from the first node of the left list to the last node of the right list and vice versa.

    Dry Run

    Code Implementation

    public class PrepBytes
    {
        static class Node
        {
            int data;
            Node left = null;
            Node right = null;
         
            Node(int data) {
                this.data = data;
            }
        }
    
        static Node concatenateLists(Node lList, Node rList)
        {
            // If the left list is null, return the right list.
            if (lList == null)
                return rList;
            
            // If the right list is null, return the right list.
            if (rList == null)
                return lList;
      
            // Create a variable to store the last node of the left list.
            Node llast = lList.left;
      
            // Create a variable to store the last node of the left list.
            Node rLast = rList.left;
      
            // Create a link from last node of the left list to
            // the first node of the right list and vice versa.
            llast.right = rList;
            rList.left = llast;
      
            // Create a link from first node of the left list to
            // last node of the right list and vice versa.
            lList.left = rLast;
            rLast.right = lList;
      
            // Return head of the left list
            return lList;
        }
      
    
        // This function will convert a tree rooted at this node to a    
        // circular doubly linked list.
        static Node convertToCircularDLL(Node root)
        {
            // Base case
            if (root == null)
                return null;
      
            // Recursively convert left subtree
            Node leftList = convertToCircularDLL(root.left);
      
            // Recursively convert right subtree
            Node rightList = convertToCircularDLL(root.right);
            
            root.left = root.right = root;
            
            
            // Concatenate leftList with root.
            Node LR = concatenateLists(leftList, root);
            
            // Concatenate the list we got after concatenating leftList and root with rightList.        
            Node LRR = concatenateLists(LR, rightList);
            
            return LRR;
            
        }
        
        // After the binary tree is successfully converted to circular doubly linked list
        // we will print the final circular doubly linked list using this method.
        public static void printCircularDLL(Node head)
        {
            Node curr = head;
            System.out.print(curr.data + " ");
            curr = curr.right;
            
            while (curr != head)
            {
                System.out.print(curr.data + " ");
                curr = curr.right;
            }
            
        }
     
        public static void main(String[] args)
        {
            Node root = new Node(0);
            root.left = new Node(2);
            root.right = new Node(3);
            root.left.left = new Node(7);
            root.left.right = new Node(8);
            root.right.left = new Node(9);
            root.right.right = new Node(10);
     
            Node head = convertToCircularDLL(root);
            printCircularDLL(head);
        }
    }
    

    Output

    7 2 8 0 9 3 10

    Time Complexity: O(n), where n is the total number of nodes in the given binary tree. To convert the given binary tree to the circular doubly linked list we traverse the binary tree, which takes linear time. It is not possible to solve this problem in time less than linear time because that would mean we do not traverse each node and have missed some nodes.

    Space complexity: O(h), where h is the height of the binary tree. At any instant, the space occupied by the recursive stack is at most h.

    So, in this blog, we have tried to explain how you can convert a given binary Tree to a circular doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

  • Leave a Reply

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