Problem Statement#
Convert a binary tree to a doubly linked list so that the order of the doubly linked list is the same as an in-order traversal of the binary tree. After conversion, the left pointer of the node should be pointing to the previous node in the doubly linked list, and the right pointer should be pointing to the next node in the doubly linked list.
Consider the tree below:
Its in-order traversal will be 25, 30, 50, 60, 75, 100, 125, 200, 350. So, the output doubly linked list should look like so:
BinaryTreeNode* convert_to_linked_list(BinaryTreeNode* root) {//TODO: Write - Your - Codereturn root;}
Solution#
// merge(fuse) two sorted linked listsBinaryTreeNode* concatenate_lists(BinaryTreeNode* head1,BinaryTreeNode* head2) {if (head1 == nullptr) {return head2;}if (head2 == nullptr) {return head1;}// use left for previous.// use right for next.BinaryTreeNode* tail1 = head1->left;BinaryTreeNode* tail2 = head2 -> left;tail1->right = head2;head2->left = tail1;head1->left = tail2;tail2->right = head1;return head1;}BinaryTreeNode* convert_to_linked_list(BinaryTreeNode* root) {if (root == nullptr) {return nullptr;}BinaryTreeNode* list1 = convert_to_linked_list(root->left);BinaryTreeNode* list2 = convert_to_linked_list(root->right);root->left = root->right = root;BinaryTreeNode* result = concatenate_lists(list1, root);result = concatenate_lists(result, list2);return result;}vector<int> get_vector(BinaryTreeNode* head) {vector<int> r;if (head == nullptr) {return r;}BinaryTreeNode* temp = head;do {r.push_back(temp->data);temp = temp->right;}while (temp != head);return r;}int main() {vector<int> orig_data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};BinaryTreeNode* root = create_BST(orig_data);vector<int> all_data = binary_tree_to_vector(root);BinaryTreeNode* head = convert_to_linked_list(root);vector<int> v = get_vector(head);for(int x : v){cout<<x<<",";}assert(is_equal(v, all_data));return 0;}
Solution Explanation#
Runtime Complexity#
Linear, O(n).
Runtime complexity is based on the number of nodes in the tree.
Memory Complexity#
Linear, O(h).
Recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of binary tree ‘h’. It will be O(log n) for balanced tree and in worst case can be O(n).
Solution Breakdown#
In an in-order traversal, first the left sub-tree is traversed, then the root is visited, and finally the right sub-tree is traversed.
One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order traversal of the binary tree, keep inserting each element output into the doubly linked list. But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list in-place i.e. we should not create new nodes for the doubly linked list.
This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified.
Start with the root node and solve left and right sub-trees recursively
At each step, once left and right sub-trees have been processed:
Fuse output of left subtree with root to make the intermediate result
Fuse intermediate result (built in the previous step) with output from the right sub-tree to make the final result of the current recursive call
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!
Free Resources
