DSA Series Chapter 28 : Convert Binary Tree to Doubly Linked List (DLL)(C Version (Inorder Conversion)
.png)
[Follow here] for daily coding insights
DSA Series Chapter 28 : Convert Binary Tree to Doubly Linked List (DLL)(C Version (Inorder Conversion)
1. Objective
To convert a Binary Tree into a Doubly Linked List (DLL) such that:
DLL nodes follow inorder sequence of the binary tree
Conversion is done in-place (no new nodes created)
2. Definition (Exam-Oriented)
Converting a binary tree to a doubly linked list means rearranging the tree pointers so that:
leftpointer acts asprev
rightpointer acts asnextNodes appear in inorder traversal order
3. Example
Binary Tree
10
/ \
5 20
/ \
3 8
Inorder Traversal
3 5 8 10 20
Resulting DLL
NULL <-> 3 <-> 5 <-> 8 <-> 10 <-> 20 <-> NULL
4. Key Observations
Inorder traversal gives sorted order for BST
We maintain:
prev→ previously processed nodehead→ first node of DLL
5. Core Idea
Perform inorder traversal
Link current node with
prevUpdate
prevafter each visit
6. Node Structure
struct Node
{
int data;
struct Node *left;
struct Node *right;
};
7. Conversion Function
void convertToDLL(struct Node* root, struct Node** head, struct Node** prev)
{
if (root == NULL)
return;
convertToDLL(root->left, head, prev);
if (*prev == NULL)
*head = root;
else
{
root->left = *prev;
(*prev)->right = root;
}
*prev = root;
convertToDLL(root->right, head, prev);
}
8. Line-by-Line Explanation
Traverse left subtree
If first node, assign as
headElse connect:
current->left = prev
prev->right = current
Update
prevTraverse right subtree
9. Complete C Program
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *left;
struct Node *right;
};
struct Node* createNode(int data)
{
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void convertToDLL(struct Node* root, struct Node** head, struct Node** prev)
{
if (root == NULL)
return;
convertToDLL(root->left, head, prev);
if (*prev == NULL)
*head = root;
else
{
root->left = *prev;
(*prev)->right = root;
}
*prev = root;
convertToDLL(root->right, head, prev);
}
void printDLL(struct Node* head)
{
struct Node* temp = head;
while (temp)
{
printf("%d ", temp->data);
temp = temp->right;
}
}
int main()
{
struct Node* root = createNode(10);
root->left = createNode(5);
root->right = createNode(20);
root->left->left = createNode(3);
root->left->right = createNode(8);
struct Node* head = NULL;
struct Node* prev = NULL;
convertToDLL(root, &head, &prev);
printf("Doubly Linked List: ");
printDLL(head);
return 0;
}
10. Output
Doubly Linked List: 3 5 8 10 20
11. Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(h)
Comments
Post a Comment