Convert a Binary Tree to a Circular Doubly Link List

Last Updated : 10 Jan, 2023

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 the converted Circular Linked List.
The order of nodes in the List must be the same as in Inorder for the given Binary Tree.
The first node of Inorder traversal must be the head node of the Circular List.

Examples:

tree to list

Convert a Binary Tree to a Circular Doubly Link List using Recursion:

The idea is to make a general-purpose function that concatenates two given circular doubly lists

Follow the steps below to solve the problem:

Recursively convert the left subtree to a circular DLL. Let the converted list be leftList.
Recursively convert the right subtree to a circular DLL. Let the converted list be rightList.
Make a circular linked list of roots of the tree, and make the left and right root points to themselves.
Concatenate leftList with the list of the single root node.
Concatenate the list produced in the step above with rightList.

Note: The above approach traverses the tree in a Postorder fashion. We can traverse in an inorder fashion also. We can first concatenate left subtree and root, then recur for the right subtree and concatenate the result with left-root concatenation.

How do Concatenate two circular DLLs?

Get the last node of the left list. Retrieving the last node is an O(1) operation since the prev pointer of the head points to the last node of the list.
Connect it with the first node of the right list
Get the last node of the second list
Connect it with the head of the list.

Below are implementations of the above idea:

C++

// C++ Program to convert a Binary Tree 
// to a Circular Doubly Linked List 
#include <iostream> 
using namespace std; 
  
// To represents a node of a Binary Tree 
struct Node { 
    struct Node *left, *right; 
    int data; 
}; 
  
// A function that appends rightList at the end 
// of leftList. 
Node* concatenate(Node* leftList, Node* rightList) 
{ 
    // If either of the list is empty 
    // then return the other list 
    if (leftList == NULL) 
        return rightList; 
    if (rightList == NULL) 
        return leftList; 
  
    // Store the last Node of left List 
    Node* leftLast = leftList->left; 
  
    // Store the last Node of right List 
    Node* rightLast = rightList->left; 
  
    // Connect the last node of Left List 
    // with the first Node of the right List 
    leftLast->right = rightList; 
    rightList->left = leftLast; 
  
    // Left of first node points to 
    // the last node in the list 
    leftList->left = rightLast; 
  
    // Right of last node refers to the first 
    // node of the List 
    rightLast->right = leftList; 
  
    return leftList; 
} 
  
// Function converts a tree to a circular Linked List 
// and then returns the head of the Linked List 
Node* bTreeToCList(Node* root) 
{ 
    if (root == NULL) 
        return NULL; 
  
    // Recursively convert left and right subtrees 
    Node* left = bTreeToCList(root->left); 
    Node* right = bTreeToCList(root->right); 
  
    // Make a circular linked list of single node 
    // (or root). To do so, make the right and 
    // left pointers of this node point to itself 
    root->left = root->right = root; 
  
    // Step 1 (concatenate the left list with the list 
    //         with single node, i.e., current node) 
    // Step 2 (concatenate the returned list with the 
    //         right List) 
    return concatenate(concatenate(left, root), right); 
} 
  
// Display Circular Link List 
void displayCList(Node* head) 
{ 
    cout << "Circular Linked List is :\n"; 
    Node* itr = head; 
    do { 
        cout << itr->data << " "; 
        itr = itr->right; 
    } while (head != itr); 
    cout << "\n"; 
} 
  
// Create a new Node and return its address 
Node* newNode(int data) 
{ 
    Node* temp = new Node(); 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
// Driver Program to test above function 
int main() 
{ 
    Node* root = newNode(10); 
    root->left = newNode(12); 
    root->right = newNode(15); 
    root->left->left = newNode(25); 
    root->left->right = newNode(30); 
    root->right->left = newNode(36); 
  
    Node* head = bTreeToCList(root); 
    displayCList(head); 
  
    return 0; 
} 
  
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C Program to convert a Binary Tree 
// to a Circular Doubly Linked List 
#include <stdio.h> 
#include <stdlib.h> 
  
// To represents a node of a Binary Tree 
typedef struct Node { 
    struct Node *left, *right; 
    int data; 
} Node; 
  
// A function that appends rightList at the end 
// of leftList. 
Node* concatenate(Node* leftList, Node* rightList) 
{ 
    // If either of the list is empty 
    // then return the other list 
    if (leftList == NULL) 
        return rightList; 
    if (rightList == NULL) 
        return leftList; 
  
    // Store the last Node of left List 
    Node* leftLast = leftList->left; 
  
    // Store the last Node of right List 
    Node* rightLast = rightList->left; 
  
    // Connect the last node of Left List 
    // with the first Node of the right List 
    leftLast->right = rightList; 
    rightList->left = leftLast; 
  
    // Left of first node points to 
    // the last node in the list 
    leftList->left = rightLast; 
  
    // Right of last node refers to the first 
    // node of the List 
    rightLast->right = leftList; 
  
    return leftList; 
} 
  
// Function converts a tree to a circular Linked List 
// and then returns the head of the Linked List 
Node* bTreeToCList(Node* root) 
{ 
    if (root == NULL) 
        return NULL; 
  
    // Recursively convert left and right subtrees 
    Node* left = bTreeToCList(root->left); 
    Node* right = bTreeToCList(root->right); 
  
    // Make a circular linked list of single node 
    // (or root). To do so, make the right and 
    // left pointers of this node point to itself 
    root->left = root->right = root; 
  
    // Step 1 (concatenate the left list with the list 
    //         with single node, i.e., current node) 
    // Step 2 (concatenate the returned list with the 
    //         right List) 
    return concatenate(concatenate(left, root), right); 
} 
  
// Display Circular Link List 
void displayCList(Node* head) 
{ 
    printf("Circular Linked List is :\n"); 
    Node* itr = head; 
    do { 
        printf("%d ", itr->data); 
        itr = itr->right; 
    } while (head != itr); 
    printf("\n"); 
} 
  
// Create a new Node and return its address 
Node* newNode(int data) 
{ 
    Node* temp = (Node*)malloc(sizeof(Node)); 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
// Driver Program to test above function 
int main() 
{ 
    Node* root = newNode(10); 
    root->left = newNode(12); 
    root->right = newNode(15); 
    root->left->left = newNode(25); 
    root->left->right = newNode(30); 
    root->right->left = newNode(36); 
  
    Node* head = bTreeToCList(root); 
    displayCList(head); 
  
    return 0; 
} 
  
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java Program to convert a Binary Tree to a 
// Circular Doubly Linked List 
  
// Node class represents a Node of a Tree 
class Node { 
    int val; 
    Node left, right; 
  
    public Node(int val) 
    { 
        this.val = val; 
        left = right = null; 
    } 
} 
  
// A class to represent a tree 
class Tree { 
    Node root; 
    public Tree() { root = null; } 
  
    // concatenate both the lists and returns the head 
    // of the List 
    public Node concatenate(Node leftList, Node rightList) 
    { 
        // If either of the list is empty, then 
        // return the other list 
        if (leftList == null) 
            return rightList; 
        if (rightList == null) 
            return leftList; 
  
        // Store the last Node of left List 
        Node leftLast = leftList.left; 
  
        // Store the last Node of right List 
        Node rightLast = rightList.left; 
  
        // Connect the last node of Left List 
        // with the first Node of the right List 
        leftLast.right = rightList; 
        rightList.left = leftLast; 
  
        // left of first node refers to 
        // the last node in the list 
        leftList.left = rightLast; 
  
        // Right of last node refers to the first 
        // node of the List 
        rightLast.right = leftList; 
  
        // Return the Head of the List 
        return leftList; 
    } 
  
    // Method converts a tree to a circular 
    // Link List and then returns the head 
    // of the Link List 
    public Node bTreeToCList(Node root) 
    { 
        if (root == null) 
            return null; 
  
        // Recursively convert left and right subtrees 
        Node left = bTreeToCList(root.left); 
        Node right = bTreeToCList(root.right); 
  
        // Make a circular linked list of single node 
        // (or root). To do so, make the right and 
        // left pointers of this node point to itself 
        root.left = root.right = root; 
  
        // Step 1 (concatenate the left list with the list 
        //         with single node, i.e., current node) 
        // Step 2 (concatenate the returned list with the 
        //         right List) 
        return concatenate(concatenate(left, root), right); 
    } 
  
    // Display Circular Link List 
    public void display(Node head) 
    { 
        System.out.println("Circular Linked List is :"); 
        Node itr = head; 
        do { 
            System.out.print(itr.val + " "); 
            itr = itr.right; 
        } while (itr != head); 
        System.out.println(); 
    } 
} 
  
// Driver Code 
class Main { 
    public static void main(String args[]) 
    { 
        // Build the tree 
        Tree tree = new Tree(); 
        tree.root = new Node(10); 
        tree.root.left = new Node(12); 
        tree.root.right = new Node(15); 
        tree.root.left.left = new Node(25); 
        tree.root.left.right = new Node(30); 
        tree.root.right.left = new Node(36); 
  
        // head refers to the head of the Link List 
        Node head = tree.bTreeToCList(tree.root); 
  
        // Display the Circular LinkedList 
        tree.display(head); 
    } 
}

Python3

# Python3 Program to convert a Binary 
# Tree to a Circular Doubly Linked List 
  
  
class newNode: 
    def __init__(self, data): 
        self.data = data 
        self.left = self.right = None
  
# A function that appends rightList 
# at the end of leftList. 
  
  
def concatenate(leftList, rightList): 
  
    # If either of the list is empty 
    # then return the other list 
    if (leftList == None): 
        return rightList 
    if (rightList == None): 
        return leftList 
  
    # Store the last Node of left List 
    leftLast = leftList.left 
  
    # Store the last Node of right List 
    rightLast = rightList.left 
  
    # Connect the last node of Left List 
    # with the first Node of the right List 
    leftLast.right = rightList 
    rightList.left = leftLast 
  
    # Left of first node points to 
    # the last node in the list 
    leftList.left = rightLast 
  
    # Right of last node refers to 
    # the first node of the List 
    rightLast.right = leftList 
  
    return leftList 
  
# Function converts a tree to a circular 
# Linked List and then returns the head 
# of the Linked List 
  
  
def bTreeToCList(root): 
    if (root == None): 
        return None
  
    # Recursively convert left and 
    # right subtrees 
    left = bTreeToCList(root.left) 
    right = bTreeToCList(root.right) 
  
    # Make a circular linked list of single 
    # node (or root). To do so, make the 
    # right and left pointers of this node 
    # point to itself 
    root.left = root.right = root 
  
    # Step 1 (concatenate the left list 
    #          with the list with single 
    #         node, i.e., current node) 
    # Step 2 (concatenate the returned list 
    #          with the right List) 
    return concatenate(concatenate(left, 
                                   root), right) 
  
# Display Circular Link List 
  
  
def displayCList(head): 
    print("Circular Linked List is :") 
    itr = head 
    first = 1
    while (head != itr or first): 
        print(itr.data, end=" ") 
        itr = itr.right 
        first = 0
    print() 
  
  
# Driver Code 
if __name__ == '__main__': 
    root = newNode(10) 
    root.left = newNode(12) 
    root.right = newNode(15) 
    root.left.left = newNode(25) 
    root.left.right = newNode(30) 
    root.right.left = newNode(36) 
  
    head = bTreeToCList(root) 
    displayCList(head) 
  
# This code is contributed by PranchalK 

C#

// C# Program to convert a Binary Tree 
// to a Circular Doubly Linked List 
using System; 
  
// Node class represents a Node of a Tree 
public class Node { 
    public int val; 
    public Node left, right; 
  
    public Node(int val) 
    { 
        this.val = val; 
        left = right = null; 
    } 
} 
  
// A class to represent a tree 
public class Tree { 
    internal Node root; 
    public Tree() { root = null; } 
  
    // concatenate both the lists 
    // and returns the head of the List 
    public virtual Node concatenate(Node leftList, 
                                    Node rightList) 
    { 
        // If either of the list is empty, 
        // then return the other list 
        if (leftList == null) { 
            return rightList; 
        } 
        if (rightList == null) { 
            return leftList; 
        } 
  
        // Store the last Node of left List 
        Node leftLast = leftList.left; 
  
        // Store the last Node of right List 
        Node rightLast = rightList.left; 
  
        // Connect the last node of Left List 
        // with the first Node of the right List 
        leftLast.right = rightList; 
        rightList.left = leftLast; 
  
        // left of first node refers to 
        // the last node in the list 
        leftList.left = rightLast; 
  
        // Right of last node refers to 
        // the first node of the List 
        rightLast.right = leftList; 
  
        // Return the Head of the List 
        return leftList; 
    } 
  
    // Method converts a tree to a circular 
    // Link List and then returns the head 
    // of the Link List 
    public virtual Node bTreeToCList(Node root) 
    { 
        if (root == null) { 
            return null; 
        } 
  
        // Recursively convert left 
        // and right subtrees 
        Node left = bTreeToCList(root.left); 
        Node right = bTreeToCList(root.right); 
  
        // Make a circular linked list of single 
        // node (or root). To do so, make the 
        // right and left pointers of this node 
        // point to itself 
        root.left = root.right = root; 
  
        // Step 1 (concatenate the left list with 
        //          the list with single node, 
        //        i.e., current node) 
        // Step 2 (concatenate the returned list 
        //           with the right List) 
        return concatenate(concatenate(left, root), right); 
    } 
  
    // Display Circular Link List 
    public virtual void display(Node head) 
    { 
        Console.WriteLine("Circular Linked List is :"); 
        Node itr = head; 
        do { 
            Console.Write(itr.val + " "); 
            itr = itr.right; 
        } while (itr != head); 
        Console.WriteLine(); 
    } 
} 
  
// Driver Code 
public class GFG { 
    public static void Main(string[] args) 
    { 
        // Build the tree 
        Tree tree = new Tree(); 
        tree.root = new Node(10); 
        tree.root.left = new Node(12); 
        tree.root.right = new Node(15); 
        tree.root.left.left = new Node(25); 
        tree.root.left.right = new Node(30); 
        tree.root.right.left = new Node(36); 
  
        // head refers to the head of the Link List 
        Node head = tree.bTreeToCList(tree.root); 
  
        // Display the Circular LinkedList 
        tree.display(head); 
    } 
} 
  
// This code is contributed by Shrikant13

Javascript

<script> 
// javascript Program to convert a Binary Tree to a 
// Circular Doubly Linked List 
  
// Node class represents a Node of a Tree 
class Node { 
    constructor(val) { 
        this.val = val; 
        this.left = null; 
        this.right = null; 
    } 
} 
  
// A class to represent a  
  
        var root = null; 
  
  
    // concatenate both the lists and returns the head 
    // of the List 
     function concatenate(leftList,  rightList) { 
        // If either of the list is empty, then 
        // return the other list 
        if (leftList == null) 
            return rightList; 
        if (rightList == null) 
            return leftList; 
  
        // Store the last Node of left List 
        var leftLast = leftList.left; 
  
        // Store the last Node of right List 
        var rightLast = rightList.left; 
  
        // Connect the last node of Left List 
        // with the first Node of the right List 
        leftLast.right = rightList; 
        rightList.left = leftLast; 
  
        // left of first node refers to 
        // the last node in the list 
        leftList.left = rightLast; 
  
        // Right of last node refers to the first 
        // node of the List 
        rightLast.right = leftList; 
  
        // Return the Head of the List 
        return leftList; 
    } 
  
    // Method converts a  to a circular 
    // Link List and then returns the head 
    // of the Link List 
     function bTreeToCList(root) { 
        if (root == null) 
            return null; 
  
        // Recursively convert left and right subtrees 
        var left = bTreeToCList(root.left); 
        var right = bTreeToCList(root.right); 
  
        // Make a circular linked list of single node 
        // (or root). To do so, make the right and 
        // left pointers of this node point to itself 
        root.left = root.right = root; 
  
        // Step 1 (concatenate the left list with the list 
        // with single node, i.e., current node) 
        // Step 2 (concatenate the returned list with the 
        // right List) 
        return concatenate(concatenate(left, root), right); 
    } 
  
    // Display Circular Link List 
     function display(head) { 
        document.write("Circular Linked List is :<br/>"); 
        var itr = head; 
        do { 
            document.write(itr.val + " "); 
            itr = itr.right; 
        } while (itr != head); 
        document.write(); 
    } 
  
  
       // Driver Code 
  
      
        // Build the  
        root = new Node(10); 
        root.left = new Node(12); 
        root.right = new Node(15); 
        root.left.left = new Node(25); 
        root.left.right = new Node(30); 
        root.right.left = new Node(36); 
  
        // head refers to the head of the Link List 
        var head = bTreeToCList(root); 
  
        // Display the Circular LinkedList 
        display(head); 
  
// This code contributed by umadevi9616 
</script>

Output

Circular Linked List is :
25 12 30 10 36 15

Time Complexity: O(N), As every node is visited at most once.
Auxiliary space: O(log N), The extra space is used in the recursion call stack which can grow up to a maximum size of logN as it is a binary tree.

Convert a Binary Tree to a Circular Doubly Link List by Inorder Traversal:

The idea is to do in-order traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable, say prev. For every visited node, make it the next of the prev and set previous of this node as prev.

Follow the steps below to solve the problem:

First convert the binary tree into doubly linked list refer to this post Convert a given Binary Tree to Doubly Linked List.
Now convert this Doubly Linked List to circular Doubly linked list by connecting first and last node.

Below is the implementation of the above approach.

C++

// A C++ program for in-place conversion of Binary Tree to 
// CDLL 
#include <iostream> 
using namespace std; 
  
/* A binary tree node has - data , left and right pointers 
 */
struct Node { 
    int data; 
    Node* left; 
    Node* right; 
}; 
// A utility function that converts given binary tree to 
// a doubly linked list 
// root --> the root of the binary tree 
// head --> head of the created doubly linked list 
Node* BTree2DoublyLinkedList(Node* root, Node** head) 
{ 
    // Base case 
    if (root == NULL) 
        return root; 
  
    // Initialize previously visited node as NULL. This is 
    // static so that the same value is accessible in all 
    // recursive calls 
    static Node* prev = NULL; 
  
    // Recursively convert left subtree 
    BTree2DoublyLinkedList(root->left, head); 
  
    // Now convert this node 
    if (prev == NULL) 
        *head = root; 
    else { 
        root->left = prev; 
        prev->right = root; 
    } 
    prev = root; 
  
    // Finally convert right subtree 
    BTree2DoublyLinkedList(root->right, head); 
    return prev; 
} 
// A simple recursive function to convert a given Binary 
// tree to Circular Doubly Linked List using a utility 
// function root --> Root of Binary Tree tail --> Pointer to 
// tail node of created circular doubly linked list 
Node* BTree2CircularDoublyLinkedList(Node* root) 
{ 
    Node* head = NULL; 
    Node* tail = BTree2DoublyLinkedList(root, &head); 
    // make the changes to convert a DLL to CDLL 
    tail->right = head; 
    head->left = tail; 
    // return the head of the created CDLL 
    return head; 
} 
  
/* Helper function that allocates a new node with the 
given data and NULL left and right pointers. */
Node* newNode(int data) 
{ 
    Node* new_node = new Node; 
    new_node->data = data; 
    new_node->left = new_node->right = NULL; 
    return (new_node); 
} 
  
/* Function to print nodes in a given circular doubly linked 
 * list */
void printList(Node* head) 
{ 
    if (head == NULL) 
        return; 
    Node* ptr = head; 
    do { 
        cout << ptr->data << " "; 
        ptr = ptr->right; 
    } while (ptr != head); 
} 
  
/* Driver program to test above functions*/
int main() 
{ 
    // Let us create the tree shown in above diagram 
    Node* root = newNode(10); 
    root->left = newNode(12); 
    root->right = newNode(15); 
    root->left->left = newNode(25); 
    root->left->right = newNode(30); 
    root->right->left = newNode(36); 
  
    // Convert to DLL 
    Node* head = BTree2CircularDoublyLinkedList(root); 
  
    // Print the converted list 
    printList(head); 
  
    return 0; 
} 
  
// This code was contributed by Abhijeet 
// Kumar(abhijeet19403)

Java

// A Java program for in-place conversion of Binary Tree to 
// CDLL 
  
// A binary tree node has - data, left pointer and right 
// pointer 
class Node { 
    int data; 
    Node left, right; 
    public Node(int data) 
    { 
        this.data = data; 
        left = right = null; 
    } 
} 
  
class BinaryTree { 
    Node root; 
    // head --> Pointer to head node of created doubly 
    // linked list 
    Node head; 
  
    // Initialize previously visited node as NULL. This is 
    // static so that the same value is accessible in all 
    // recursive calls 
    static Node prev = null; 
  
    // A simple utility recursive function to convert a 
    // given Binary tree to Doubly Linked List root --> Root 
    // of Binary Tree 
    void BTree2DoublyLinkedList(Node root) 
    { 
        // Base case 
        if (root == null) 
            return; 
  
        // Recursively convert left subtree 
        BTree2DoublyLinkedList(root.left); 
  
        // Now convert this node 
        if (prev == null) 
            head = root; 
        else { 
            root.left = prev; 
            prev.right = root; 
        } 
        prev = root; 
  
        // Finally convert right subtree 
        BTree2DoublyLinkedList(root.right); 
    } 
    // A simple function to convert a given binary tree to 
    // Circular doubly linked list 
    // using a utility function 
    void BTree2CircularDoublyLinkedList(Node root) 
    { 
        BTree2DoublyLinkedList(root); 
        // make the changes to convert a DLL to CDLL 
        prev.right = head; 
        head.left = prev; 
    } 
  
    /* Function to print nodes in a given doubly linked list 
     */
    void printList(Node node) 
    { 
        if (node == null) 
            return; 
        Node curr = node; 
        do { 
            System.out.print(curr.data + " "); 
            curr = curr.right; 
        } while (curr != node); 
    } 
  
    // Driver program to test above functions 
    public static void main(String[] args) 
    { 
        // Let us create the tree as shown in above diagram 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(10); 
        tree.root.left = new Node(12); 
        tree.root.right = new Node(15); 
        tree.root.left.left = new Node(25); 
        tree.root.left.right = new Node(30); 
        tree.root.right.left = new Node(36); 
  
        // convert to DLL 
        tree.BTree2CircularDoublyLinkedList(tree.root); 
  
        // Print the converted List 
        tree.printList(tree.head); 
    } 
} 
// This code has been contributed by Abhijeet 
// Kumar(abhijeet19403)

Python

# A python program for in-place conversion of Binary Tree to DLL 
# A binary tree node has data, left pointers and right pointers 
class Node: 
    def __init__(self, val): 
        self.data = val 
        self.left = None
        self.right = None
  
# head --> Pointer to head node of created doubly linked list 
head = None
  
# Initialize previously visited node as NULL. This is 
# so that the same value is accessible in all recursive 
# calls 
prev = None
  
# A simple recursive function to convert a given Binary tree 
# to Doubly Linked List 
# root --> Root of Binary Tree 
def BinaryTree2DoubleLinkedList(root): 
  
    # Base case 
    if (root == None): 
        return
  
    # Recursively convert left subtree 
    BinaryTree2DoubleLinkedList(root.left) 
  
    # Now convert this node 
    global prev, head 
    if (prev == None): 
        head = root 
    else: 
        root.left = prev 
        prev.right = root 
    prev = root 
  
    # Finally convert right subtree 
    BinaryTree2DoubleLinkedList(root.right) 
  
# Function to print nodes in a given doubly linked list 
  
  
def printList(node): 
    while (node != None): 
        print(node.data) 
        node = node.right 
  
  
# Driver program to test above functions 
# Let us create the tree as shown in above diagram 
root = Node(10) 
root.left = Node(12) 
root.right = Node(15) 
root.left.left = Node(25) 
root.left.right = Node(30) 
root.right.left = Node(36) 
  
# convert to DLL 
BinaryTree2DoubleLinkedList(root) 
  
# Print the converted List 
printList(head) 
  
# This code is contributed by adityamaharshi21. 

C#

// A C# program for in-place conversion of Binary Tree to 
// CDLL 
  
using System; 
  
public class Node { 
    public int data; 
    public Node left, right; 
    public Node(int data) 
    { 
        this.data = data; 
        left = right = null; 
    } 
} 
  
public class BinaryTree { 
  
    Node root; 
    // head --> Pointer to head node of created doubly 
    // linked list 
    Node head; 
  
    // Initialize previously visited node as NULL. This is 
    // static so that the same value is accessible in all 
    // recursive calls 
    static Node prev = null; 
  
    // A simple utility recursive function to convert a 
    // given Binary tree to Doubly Linked List root --> Root 
    // of Binary Tree 
    void BTree2DoublyLinkedList(Node root) 
    { 
        // Base case 
        if (root == null) 
            return; 
  
        // Recursively convert left subtree 
        BTree2DoublyLinkedList(root.left); 
  
        // Now convert this node 
        if (prev == null) 
            head = root; 
        else { 
            root.left = prev; 
            prev.right = root; 
        } 
        prev = root; 
  
        // Finally convert right subtree 
        BTree2DoublyLinkedList(root.right); 
    } 
    // A simple function to convert a given binary tree to 
    // Circular doubly linked list 
    // using a utility function 
    void BTree2CircularDoublyLinkedList(Node root) 
    { 
        BTree2DoublyLinkedList(root); 
        // make the changes to convert a DLL to CDLL 
        prev.right = head; 
        head.left = prev; 
    } 
  
    /* Function to print nodes in a given doubly linked list 
     */
    void printList(Node node) 
    { 
        if (node == null) 
            return; 
        Node curr = node; 
        do { 
            Console.Write(curr.data + " "); 
            curr = curr.right; 
        } while (curr != node); 
    } 
  
    static public void Main() 
    { 
  
        // Let us create the tree as shown in above diagram 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(10); 
        tree.root.left = new Node(12); 
        tree.root.right = new Node(15); 
        tree.root.left.left = new Node(25); 
        tree.root.left.right = new Node(30); 
        tree.root.right.left = new Node(36); 
  
        // convert to DLL 
        tree.BTree2CircularDoublyLinkedList(tree.root); 
  
        // Print the converted List 
        tree.printList(tree.head); 
    } 
} 
  
// This code is contributed by lokesh(lokeshmvs21).

Javascript

// A javascript program for in-place conversion of Binary Tree to DLL 
// A binary tree node has data, left pointers and right pointers 
class Node { 
    constructor(val) { 
        this.data = val; 
        this.left = null; 
        this.right = null; 
    } 
} 
var root; 
  
// head --> Pointer to head node of created doubly linked list 
var head; 
  
// Initialize previously visited node as NULL. This is 
// so that the same value is accessible in all recursive 
// calls 
var prev = null; 
  
// A simple recursive function to convert a given Binary tree 
// to Doubly Linked List 
// root --> Root of Binary Tree 
function BinaryTree2DoubleLinkedList(root) 
{ 
  
    // Base case 
    if (root == null) 
        return; 
          
    // Recursively convert left subtree 
    BinaryTree2DoubleLinkedList(root.left); 
      
    // Now convert this node 
    if (prev == null) 
        head = root; 
    else { 
        root.left = prev; 
        prev.right = root; 
    } 
    prev = root; 
      
    // Finally convert right subtree 
    BinaryTree2DoubleLinkedList(root.right); 
} 
  
/* Function to print nodes in a given doubly linked list */
function printList(node) { 
    while (node != null) { 
        console.log(node.data + " "); 
        node = node.right; 
    } 
} 
  
// Driver program to test above functions 
// Let us create the tree as shown in above diagram 
root = new Node(10); 
root.left = new Node(12); 
root.right = new Node(15); 
root.left.left = new Node(25); 
root.left.right = new Node(30); 
root.right.left = new Node(36); 
  
// convert to DLL 
BinaryTree2DoubleLinkedList(root); 
  
// Print the converted List 
printList(head); 
  
// This code is contributed by ishankhandelwals.

Output

25 12 30 10 36 15

Time Complexity: O(N), As every node is visited at most once.
Auxiliary space: O(log N), The extra space is used in the recursive function call stack which can grow upto a maximum size of logN.

This approach was contributed by Abhijeet Kumar

C

Chirag Agarwal

Improve

Previous Article

Convert a Binary Tree into Doubly Linked List in spiral fashion

Convert Ternary Expression to a Binary Tree

Similar Reads

Convert Binary Tree to Circular Doubly Linked List using Linear extra space

Given a Binary Tree, convert it to a Circular Doubly Linked List. The left and right pointers in nodes are to be used as previous and next pointers, respectively, in the converted Circular Linked List.The order of nodes in the List must be the same as in the order of the given Binary Tree.The first node of Inorder traversal must be the head node of

Convert an Array to a Circular Doubly Linked List

Prerequisite: Doubly Linked list, Circular Linked List, Circular Doubly Linked ListGiven an array of N elements. The task is to write a program to convert the array into a circular doubly linked list. The idea is to start traversing the array and for every array element create a new list node and assign the prev and next pointers of this node accor

Convert Binary Tree to Doubly Linked List using Morris Traversal

Given a Binary Tree (BT), convert it to a Doubly Linked List (DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal must be the head node of the DLL. Examples: Input

Convert Binary Tree to Doubly Linked List by fixing left and right pointers

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the

Convert given Binary Tree to Doubly Linked List in Linear time

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the D

Convert a Binary Tree into Doubly Linked List in spiral fashion

Given a Binary Tree, convert it into a Doubly Linked List where the nodes are represented Spirally. The left pointer of the binary tree node should act as a previous node for created DLL and the right pointer should act as the next node. The solution should not allocate extra memory for DLL nodes. It should use binary tree nodes for creating DLL i.

Convert Binary Tree to Doubly Linked List using inorder traversal

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the

Convert Binary Tree to Doubly Linked List by keeping track of visited node

Given a Binary Tree, The task is to convert it to a Doubly Linked List keeping the same order. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be the same as in Inorder for the given Binary Tree. The first node of Inorder traversal (leftmost node in BT)

Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)

Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow

Applications, Advantages and Disadvantages of Circular Doubly Linked List

The circular doubly linked list is a combination of the doubly linked list and the circular linked list. It means that this linked list is bidirectional and contains two pointers and the last pointer points to the first pointer. Applications of Circular Doubly Linked List: Music and video playlists: Circular doubly linked lists are commonly used to

Article Tags :

Practice Tags :