Convert Binary Tree to Doubly Linked List

// 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

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Convert Binary Tree to Doubly Linked List

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown