Binary Tree to a Circular Doubly Link List

Given a Binary Tree, convert it to a Circular Doubly Linked List (In-Place).

• The left and right pointers in nodes are to be used as previous and next pointers respectively in converted Circular Linked List.

• The order of nodes in List must be same as Inorder of the given Binary Tree.

• The first node of Inorder traversal must be head node of the Circular List.

Example:

class Solution {
    Node last;

    Node bToDLL(Node root) {
        if (root == null)
            return root;
        Node leftEnd = bToDLL(root.left);
        if (last != null) {
            last.right = root;
            root.left = last;
        }
        last = root;
        Node rightEnd = bToDLL(root.right);
        root.right = rightEnd;
        if (rightEnd != null)
            rightEnd.left = root;
        return leftEnd == null ? root : leftEnd;
    }

    Node bTreeToClist(Node root) {
        if (root == null)
            return root;
        Node head = bToDLL(root);
        head.left = last;
        last.right = head;
        return head;
    }
}