Skip to content
Shadow Cipher

Merge2BST LinkedList

#include <bits/stdc++.h> // Includes common standard libraries (iostream, vector, etc.)
#include "BST.h"         // Assumed to contain Node class, takeinput, levelOrderTraversal


using namespace std;     // Use the standard namespace


// Note: The Node class, takeinput, and levelOrderTraversal
// are assumed to be defined in "BST.h".
/*
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) { // Constructor for Node
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};


void takeinput(Node* &root) { ... }
void levelOrderTraversal(Node* root) { ... }
*/


// Function to flatten a BST into a sorted Doubly Linked List (DLL) in-place.
// Uses reverse in-order traversal (Right -> Root -> Left).
// 'head' will point to the current start of the DLL (the smallest element added so far).
// Time Complexity: O(N)
// Space Complexity: O(H) for recursion stack (H = height of BST)
void flattenBST(Node* root, Node* &head) {
    // Base case: If current node is NULL, return.
    if(root == NULL) {
        return;
    }


    // 1. Recursively flatten the right subtree. When this call returns,
    // 'head' points to the DLL formed from the right subtree.
    flattenBST(root->right, head);


    // 2. Process the current 'root' node.
    // Link current 'root's right pointer to the head of the DLL formed so far (its successor).
    root->right = head;


    // If there's a successor (head is not NULL), link its left pointer back to the current 'root'.
    if(head != NULL) {
        head->left = root;
    }


    // Update 'head' to be the current 'root'. 'root' is now the new smallest element in our DLL.
    head = root;


    // 3. Recursively flatten the left subtree. These elements will be prepended to 'head'.
    flattenBST(root->left, head);
}


// Function to merge two sorted Doubly Linked Lists into a single sorted DLL.
// Time Complexity: O(N1 + N2)
// Space Complexity: O(1) (in-place merging)
Node* mergeLinkedhead(Node* head1, Node* head2) {
    Node* head = NULL; // Head of the merged DLL
    Node* tail = NULL; // Tail of the merged DLL


    // Debugging print statements - remove in production code
    // cout << "\nBEFORE FIRST WHILE\n";


    // Merge until one of the lists is exhausted.
    while(head1 != NULL && head2 != NULL) {
        if(head1->data < head2->data) {
            // If merged list is empty, current node becomes head and tail.
            if(head == NULL) {
                head = tail = head1;
            } else { // Append to the tail of the merged list.
                tail->right = head1;
                head1->left = tail;
                tail = head1;
            }
            head1 = head1->right; // Advance head1
        } else {
            // Similar logic for head2's smaller data.
            if(head == NULL) {
                head = tail = head2;
            } else {
                tail->right = head2;
                head2->left = tail;
                tail = head2;
            }
            head2 = head2->right; // Advance head2
        }
    }


    // Debugging print statements - remove in production code
    // cout << "\nAFTER FIRST WHILE\n";


    // Append remaining nodes from head1 (if any).
    while(head1 != NULL) {
        tail->right = head1;
        head1->left = tail;
        tail = head1;
        head1 = head1->right;
    }


    // Append remaining nodes from head2 (if any).
    while(head2 != NULL) {
        tail->right = head2;
        head2->left = tail;
        tail = head2;
        head2 = head2->right;
    }


    return head; // Return the head of the merged DLL.
}


// Function to count the number of nodes in a Doubly Linked List.
// Time Complexity: O(N)
// Space Complexity: O(1)
int countNodes(Node* head) {
    int cnt = 0;
    Node* temp = head;
    while(temp != NULL) {
        cnt++;
        temp = temp->right; // Traverse using the 'right' (next) pointer.
    }
    return cnt;
}


// Function to convert a sorted Doubly Linked List into a balanced BST.
// The provided active implementation (using 'root = head; while(temp--)') is problematic.
// The commented-out code below represents the standard correct and efficient approach.
// Time Complexity: O(N)
// Space Complexity: O(log N) for recursion stack (for balanced BST)
Node* LL_2_BST(Node* &head, int n) { // Head must be passed by reference!
    // Base case: No nodes or invalid count.
    if(n <= 0 || head == NULL) {
        return NULL;
    }


    // Recursively build the left subtree.
    // 'head' is advanced implicitly as nodes are consumed for the left subtree.
    Node* leftChild = LL_2_BST(head, n/2); // Corrected parameter name


    // The current 'head' now points to the root of the current subtree.
    Node* root = head;
    root->left = leftChild; // Link the built left subtree.


    // Advance 'head' past the current root node, for the right subtree.
    head = head->right;


    // Recursively build the right subtree.
    // 'n - n/2 - 1' is the number of nodes remaining for the right subtree.
    root->right = LL_2_BST(head, n - n/2 - 1);


    return root; // Return the root of the current balanced subtree.


    // Original provided active code (potentially problematic for 'head' advancement):
    // int temp = n/2;
    // Node* root = head;
    // while(temp--) {
    //     root = root->right;
    // }
    // root->left = LL_2_BST(head, n/2); // 'head' is not properly advanced for this call
    // root->right = LL_2_BST(root->right, n-n/2-1);
    // return root;
    // Note: The commented-out correct logic above requires 'head' to be updated recursively.
    // The active code's 'head' parameter is passed by value, not reference.
}




// Main function to merge two BSTs into a single balanced BST using the DLL approach.
// Time Complexity: O(N1 + N2)
// Space Complexity: O(H_original) due to flattenBST, then O(log N) for LL_2_BST.
Node* MergeBST(Node* root1, Node* root2) {
    // Step 1: Convert both BSTs into sorted Doubly Linked Lists.
    Node* head1 = NULL; // Head of DLL from BST1
    Node* head2 = NULL; // Head of DLL from BST2


    flattenBST(root1, head1); // Flatten BST1 into DLL head1
    flattenBST(root2, head2); // Flatten BST2 into DLL head2


    // Crucial step: Set 'left' pointer of the first node in each DLL to NULL,
    // as flattenBST might leave it pointing to an old parent from the BST structure.
    if (head1 != NULL) head1->left = NULL;
    if (head2 != NULL) head2->left = NULL;


    // Step 2: Merge the two sorted DLLs into a single sorted DLL.
    Node* mergedListHead = mergeLinkedhead(head1, head2);


    // Step 3: Convert the merged sorted DLL into a balanced BST.
    // First, count the total number of nodes in the merged DLL.
    int totalNodes = countNodes(mergedListHead);
    // Then, call LL_2_BST to build the balanced BST.
    Node* result = LL_2_BST(mergedListHead, totalNodes); // Use the correct DLL-to-BST conversion


    return result; // Return the root of the newly merged and balanced BST.
}


int main() {
    Node* root1 = NULL; // Initialize root of the first BST
    Node* root2 = NULL; // Initialize root of the second BST


    cout << "Enter data to create BST 1 (e.g., 50 40 60 70 -1) : ";
    takeinput(root1); // Build BST 1


    cout << "Enter data to create BST 2 (e.g., 55 45 35 65 47 -1) : ";
    takeinput(root2); // Build BST 2


    cout << endl << "Level Order Traversal of BST 1 : " << endl;
    levelOrderTraversal(root1); // Print BST 1


    cout << endl << "Level Order Traversal of BST 2 : " << endl;
    levelOrderTraversal(root2); // Print BST 2


    // Call the MergeBST function to get the merged and balanced BST.
    Node* result = MergeBST(root1, root2);


    // Print the level order traversal of the final merged BST from main.
    cout << endl << "Level Order Traversal of final merged BST (from main) : " << endl;
    levelOrderTraversal(result);


    return 0;
}


/*
Example Inputs (from previous prompt, still valid for this method):
BST 1: 50 40 60 70 -1
BST 2: 55 45 35 65 47 -1


Expected Merged Sorted Array/DLL:
35, 40, 45, 47, 50, 55, 60, 65, 70


Expected Merged and Balanced BST (Level Order Traversal):
(Middle element of merged array/DLL is 50, so it's the root)
          50
         /  \
        40   60
       / \   / \
      35 45 55 70
         /   /
        47  65


Output of Level Order Traversal:
50 40 60 35 45 55 70 47 65
*/

1. Binary Search Tree (BST) & Doubly Linked List (DLL) Recap

  • BST: Left children are smaller, right children are larger. In-order traversal gives sorted elements.
  • DLL: Each node has pointers to both the next (right) and previous (left) nodes.

2. Core Idea for Merging Two BSTs (DLL Approach)

This method aims to be more space-efficient than converting to arrays by performing transformations in-place (or by reusing node memory), conceptually:

  1. Convert BST to Sorted Doubly Linked List (DLL): Transform each BST into a sorted DLL. The right pointer acts as next and left pointer acts as prev. This is done in-place.
  2. Merge Two Sorted DLLs: Combine the two sorted DLLs into a single, larger sorted DLL.
  3. Convert Sorted DLL to Balanced BST: Transform the merged sorted DLL back into a balanced BST.

3. Supporting Components (Briefly)

  • Node class: Defines the structure of a BST node (data, left, right). For DLL, left acts as prev, right as next.
  • takeinput, levelOrderTraversal: Functions (assumed in BST.h) to build and visualize BSTs.

4. flattenBST(Node* root, Node* &head) Function

  • Purpose: Converts a BST into a sorted Doubly Linked List (DLL) in-place.
  • Key Idea: Uses a Reverse In-order Traversal (Right -> Root -> Left). As we visit a node, we link it to the head of the DLL built so far, and then update head to be the current node. This builds the DLL from right (largest) to left (smallest).
  • Parameters:
    • Node* root: Current node in BST traversal.
    • Node* &head: A reference to the head of the DLL being built. It’s updated in each recursive call to point to the new smallest element added.
  • Logic:
    1. Base Case: If root == NULL, return.
    2. Recurse Right: flattenBST(root->right, head); First, flatten the right subtree. When this call returns, head will point to the largest element processed from the right subtree.
    3. Process Current Node (Root):
      • root->right = head;: Link current root’s right pointer to the head of the DLL formed by elements larger than root.
      • if (head != NULL) { head->left = root; }: If head isn’t NULL (meaning there’s a successor), link its left pointer back to the current root.
      • head = root;: Update the head of the DLL to be the current root. root is now the new “smallest” element in the constructed part of the DLL.
    4. Recurse Left: flattenBST(root->left, head); Flatten the left subtree. These elements will be prepended to the head.
  • Important Post-flattening: After flattenBST returns, the left pointer of the very first node in the DLL (the globally smallest element) might not be NULL due to its original BST parent links. It must be set to NULL explicitly (head1->left = NULL; head2->left = NULL;) to form a proper DLL.

5. mergeLinkedhead(Node* head1, Node* head2) Function

  • Purpose: Merges two already sorted Doubly Linked Lists (head1, head2) into a single sorted DLL.
  • Logic: A standard iterative merge process similar to the merge step in Merge Sort, adapted for DLLs.
    1. Initialize head = NULL and tail = NULL for the merged list.
    2. Iterate while (head1 != NULL && head2 != NULL):
      • Compare head1->data and head2->data.
      • Select the node with the smaller data (let’s call it chosen_node).
      • If head is NULL (first node of merged list), set head = tail = chosen_node.
      • Else, link tail->right = chosen_node; chosen_node->left = tail; tail = chosen_node;.
      • Advance the pointer of the list from which chosen_node was taken.
    3. After the loop, one list might have remaining nodes. Append these remaining nodes to the tail of the merged list, updating left and right pointers accordingly.
    4. Return the head of the fully merged DLL.

6. countNodes(Node* head) Function

  • Purpose: A simple utility function to count the number of nodes in a DLL.
  • Logic: Traverses the DLL using temp->right until NULL is reached, incrementing a counter.

7. LL_2_BST(Node* head, int n) Function

  • Purpose: Converts a sorted Doubly Linked List into a balanced BST.
  • The Provided Code’s Logic: The active code in your example directly calculates a middle node based on n/2 steps from head and then recursively tries to build left and right subtrees. This approach is prone to errors because the head pointer is not passed by reference and updated across recursive calls, meaning the left subtree might consume nodes that the right subtree also expects.
  • The Correct/Standard Efficient Logic (Commented in your code): 
    // Node* left = LL_2_BST(head, n/2); // Build left subtree, 'head' is updated
    // Node* root = head; // Current head is the root
    // root->left = left; // Link left child
    // head = head->right; // Advance head for the right subtree
    // root->right = LL_2_BST(head, n-n/2-1); // Build right subtree
    // return root;
    • This standard approach passes head by reference (Node* &head) to ensure it’s globally updated as nodes are consumed.
    • It recursively builds the left subtree, which advances the head pointer past those nodes.
    • Then, the current head (which is now the middle element) becomes the root.
    • head is advanced one more time for the root node itself.
    • Finally, the right subtree is built from the remaining list.
    • For your provided code, the active LL_2_BST function is likely incorrect and will not produce a valid BST or will have issues with node consumption. The commented-out section shows the standard correct implementation.

8. MergeBST(Node* root1, Node* root2) Function

  • Purpose: Orchestrates the entire process of merging two BSTs using the DLL-based approach.
  • Logic Flow:
    1. Flatten BSTs: Call flattenBST for root1 to get head1 and for root2 to get head2.
    2. Correct DLL Heads: Set head1->left = NULL; and head2->left = NULL; to ensure proper DLL structure.
    3. Merge DLLs: Call mergeLinkedhead(head1, head2) to get list, the single sorted DLL.
    4. Count Nodes: Call countNodes(list) to get the total number of nodes n in the merged DLL.
    5. Convert DLL to BST: Call LL_2_BST(list, n) to transform the list into a balanced BST. (Using the correct LL_2_BST logic is critical here).
    6. Return the root of the final balanced BST.

9. Complexity Analysis

  • Let N1 be nodes in BST1 and N2 in BST2. N = N1 + N2.

  • Time Complexity: O(N)

    • flattenBST: O(N1) + O(N2) = O(N) (each node visited once).
    • mergeLinkedhead: O(N1 + N2) = O(N) (standard merge).
    • countNodes: O(N) (traverses entire list).
    • LL_2_BST: O(N) (each node visited and processed once to form BST).
    • Total: O(N).

  • Space Complexity: O(log N) or O(H_original) (dominated by recursion stack)

    • flattenBST: O(H_original) for recursion stack (can be O(N) in worst case for skewed BST).
    • mergeLinkedhead: O(1) (in-place modification of existing nodes).
    • LL_2_BST: O(log N) for recursion stack (for building a balanced BST from DLL, or O(N) if building a skewed one, but here we aim for balanced).
    • Overall, the space complexity for extra memory used is O(log N) if flattenBST’s stack is considered for a balanced input tree, or O(N) in worst case for skewed input trees. The key advantage is avoiding an O(N) array storage like the previous method.