Linked List: Given a binary tree, convert into circular doubly linked list

Problem Statement:

You are given a binary tree, you need to convert it into DLL.

Left and right pointers are used as previous and next pointers

The order of nodes in the LL should be same as inorder of binary tree

First node of inorder traversal should be the head node.

Example:

Solution Explanation:

First we will convert the binary tree into DLL.

Then we will convert DLL into circular DLL by connecting first and last node.

Now how to convert the binary tree into DLL ?

We will follow below steps:

1. Perform in-order traversal of binary tree.

2. While doing inorder traversal, we keep track of the previous node as prev.

Then for every visited node, make next to prev and set the previous of current node as prev.

Time Complexity: O(N)
Space Complexity: O(logN)

Code Solution

#include <iostream> 
using namespace std; 

struct Node 
{ 
	int data; 
	Node* left; 
	Node* right; 
}; 


Node* convert_b_tree_to_dll (Node* root, Node** head) 
{ 
	// Base case 
	if (root == NULL) 
		return root; 

	static Node* prev = NULL; 

	// convert left subtree recursively
	convert_b_tree_to_dll(root->left, head); 

	// convert the node
	if (prev == NULL) 
		*head = root; 
	else { 
		root->left = prev; 
		prev->right = root; 
	}
	prev = root; 

	// convert left subtree recursively
	convert_b_tree_to_dll(root->right, head); 
	return prev; 
} 


Node* convert_b_tree_to_circular_dll(Node* root) 
{ 
	Node* head = NULL; 
	Node* tail = convert_b_tree_to_dll(root, &head); 

	// convert DLL to CDLL
	tail->right = head; 
	head->left = tail; 


	return head; 
} 


Node* newNode(int data) 
{ 
	Node* new_node = new Node; 
	new_node->data = data; 
	new_node->left = new_node->right = NULL; 
	return (new_node); 
} 

void print_list(Node* head) 
{ 
	if (head == NULL) 
		return; 
	Node* ptr = head; 
	do { 
		cout << ptr->data << " "; 
		ptr = ptr->right; 
	} while (ptr != head); 
} 

int main() 
{ 
	Node* root = newNode(10); 
	root->left = newNode(20); 
	root->right = newNode(18); 
	root->left->left = newNode(30); 
	root->left->right = newNode(40); 
	root->right->left = newNode(66); 

	
	Node* head = convert_b_tree_to_circular_dll(root); 

	// Print the converted list 
	print_list(head); 

	return 0; 
} 

Output

30 20 40 10 66 18