Convert Binary Tree to Doubly Linked List

editor-page-cover

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:

widget

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:

widget

Hint

  • Divide and Conquer
  • Recursion
  • Fuse already processed sub-trees

Try it yourself

BinaryTreeNode* convert_to_linked_list(
    BinaryTreeNode* root) {
   //TODO: Write - Your - Code
    return root;
}

Solution

// merge(fuse) two sorted linked lists
BinaryTreeNode* 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