How will you convert a binary tree into a doubly-linked list?

1.	How will you convert a binary tree into a doubly-linked list?
Answer» In a converted doubly linked list, the left and right pointers in nodes of a binary TREE will be used as previous and next pointers, respectively. The nodes in the doubly linked list must be in the same order as the provided Binary Tree's INORDER. The HEAD node of the doubly linked list must be the first node of Inorder TRAVERSAL (leftmost node in the binary tree). void btToDLL(Node root, Node head_reference, Node previous){ if (!root) return; // RECURSIVE conversion of left subtree btToDLL(root->left, head_reference, previous); if (head_reference == NULL) head_reference = root; else { root->left = previous; previous->right = root; } previous = root; // Recursive conversion of right subtree btToDLL(root->right, head_reference, previous);} Time Complexity: O(n) Auxiliary Space: O(1)

Answer»

In a converted doubly linked list, the left and right pointers in nodes of a binary TREE will be used as previous and next pointers, respectively. The nodes in the doubly linked list must be in the same order as the provided Binary Tree's INORDER. The HEAD node of the doubly linked list must be the first node of Inorder TRAVERSAL (leftmost node in the binary tree).

void btToDLL(Node *root, Node **head_reference, Node **previous){ if (!root) return; // RECURSIVE conversion of left subtree btToDLL(root->left, head_reference, previous); if (*head_reference == NULL) *head_reference = root; else { root->left = *previous; *previous->right = root; } *previous = root; // Recursive conversion of right subtree btToDLL(root->right, head_reference, previous);}

Time Complexity: O(n)
Auxiliary Space: O(1)

Discussion

No Comment Found

Related InterviewSolutions

A given linked list is sorted based on absolute values. Write a function to sort the list based on actual values in O(n) time.
Given a linked list and a number n, you have to find the sum of the last n nodes of the linked list in a single traversal. Explain your approach in brief.
How will you modify a linked list of integers so that all even numbers appear before all odd numbers in the modified linked list? Also, keep the even and odd numbers in the same order.
A linked list of coordinates is given, with neighboring points forming either a vertical or horizontal line. Remove points in between the starting and ending points of the horizontal or vertical line from the linked list.
Construct a doubly linked list out of a ternary tree.
The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.
Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.
Extract all leaves from a Binary Tree into a Doubly Linked List (DLL).
Write a program to delete all odd positioned nodes from a circular linked list. (Consider 1-based indexing).
Why is merge sort a better option than quicksort for linked lists?