BST to Min Heap

#include <bits/stdc++.h> // Includes common standard libraries (vector, iostream, algorithm, etc.)
#include "Tree.h"        // Assumed to contain Node class definition and tree utility functions

using namespace std;     // Use the standard namespace

// Assuming Node structure from "Tree.h" is something like:
/*
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int d) {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};
Node* takeinput(Node* root) { ... } // Function to build a general binary tree (BST in this context)
void levelOrderTraversal(Node* root) { ... } // Function to print tree level by level
*/

// Function to perform inorder traversal of the BST and store node data in a vector.
// Inorder traversal of a BST yields elements in sorted (ascending) order.
// 'root': The current node.
// 'arr': The vector to store the sorted elements (passed by reference to modify).
// Time Complexity: O(N) (visits each node once)
// Space Complexity: O(H) for recursion stack + O(N) for 'arr' vector.
void inorder(Node* root, vector<int> &arr) {
    // Base case: If node is NULL, return.
    if(root == NULL) {
        return;
    }

    // Recursively traverse left subtree.
    inorder(root->left, arr);
    // Add current node's data to the vector.
    arr.push_back(root->data);
    // Recursively traverse right subtree.
    inorder(root->right, arr);
}

// Function to fill the nodes of the existing tree structure with sorted data
// in a pre-order traversal fashion. This effectively imposes the Min Heap property.
// 'root': The current node.
// 'index': Reference to an integer that tracks the current position in the sorted 'arr'.
// 'arr': The vector containing the sorted elements from the original BST.
// Time Complexity: O(N) (visits each node once)
// Space Complexity: O(H) for recursion stack. (arr is passed by value, but copy overhead is N for first call)
void fillPreorder(Node* root, int &index, vector<int> arr) {
    // Base case: If node is NULL, return.
    if(root == NULL) {
        return;
    }

    // Assign the next smallest element from the sorted array to the current node.
    // Increment index to point to the next element for subsequent nodes.
    // This imposes the Parent <= Child property as smaller values are assigned first (pre-order).
    if(index < arr.size()) {
        root->data = arr[index++];
    }

    // Recursively fill left and right subtrees in pre-order.
    fillPreorder(root->left, index, arr);
    fillPreorder(root->right, index, arr);
}

// Function to convert a Binary Search Tree (BST) into a Min Heap.
// It does this by first getting sorted elements (inorder) and then
// assigning them back to the tree structure in pre-order.
// Time Complexity: O(N)
// Space Complexity: O(N)
void BST_Heap(Node* root) {
    vector<int> arr;      // Vector to store sorted elements from BST.
    inorder(root, arr);   // Populate 'arr' with sorted elements.

    int i = 0;            // Index to keep track of elements in 'arr'.
    // Fill the existing tree nodes with sorted data using a pre-order traversal.
    // This re-arranges the values to satisfy the Min Heap property.
    fillPreorder(root, i, arr);
}

int main() {
    Node* root = NULL;

    // Assuming takeinput builds a BST from user input.
    // Example input: 4 2 6 1 3 5 7 -1 will build a BST.
    cout << "Enter data to create a Binary Search Tree (use -1 for NULL children) : ";
    takeinput(root); // Builds the BST (e.g., in a level-order fashion if takeinput is like that)

    cout << "Before conversion into Min Heap, BST (Level Order Traversal) : " << endl;
    levelOrderTraversal(root); // Prints the original BST.

    BST_Heap(root); // Perform the conversion.

    cout << "After conversion into Min Heap, Tree (Level Order Traversal) : " << endl;
    levelOrderTraversal(root); // Prints the tree after values are re-arranged.

    return 0;
}

/*
Example Input for takeinput (building a BST):
4 2 6 1 3 5 7 -1 (This input suggests a level-order input for a BST)
Corresponding BST structure:
        4
       / \
      2   6
     / \ / \
    1  3 5  7

Before conversion (level order): 4 2 6 1 3 5 7

After inorder traversal: arr = {1, 2, 3, 4, 5, 6, 7}

After fillPreorder (re-assigning values):
Root (4) gets 1
Left child (2) gets 2
Left-Left (1) gets 3
Left-Right (3) gets 4
Right child (6) gets 5
Right-Left (5) gets 6
Right-Right (7) gets 7

After conversion (level order): 1 2 5 3 4 6 7
This tree now satisfies the Min Heap property (parent <= children).
1 is root.
Children of 1 are 2, 5. (1 <= 2, 1 <= 5)
Children of 2 are 3, 4. (2 <= 3, 2 <= 4)
Children of 5 are 6, 7. (5 <= 6, 5 <= 7)

Note: While the values form a Min Heap, the *structure* might not be a "complete binary tree" unless the original BST was already complete.
The question implies maintaining the original BST structure but making its values satisfy the heap property.
*/

1. Problem Statement: Converting BST to Min Heap

• Goal: Transform a given Binary Search Tree (BST) such that its node values satisfy the Min Heap property, while retaining the original tree’s structure. This means we are only re-arranging the data within the existing nodes, not changing the tree’s shape (unless the original BST was already a complete binary tree, which is rare).
• Min Heap Property: For any node, its value is less than or equal to the values of its children (Parent $\le$ Children). The smallest element is at the root.

2. Core Idea & Approach

• Leveraging BST Inorder Traversal: An inorder traversal of a BST always yields its elements in sorted ascending order.
• Achieving Min Heap Property: If we assign the elements from this sorted list back into the nodes of the tree in a pre-order traversal sequence, the resulting tree will satisfy the Min Heap property.
  • Why Pre-order?: Pre-order visits the current node first, then its left child, then its right child. By assigning the smallest available value (from our sorted list) to the parent node, then the next smallest to its left child, and so on, we naturally ensure that the parent’s value is less than or equal to its children’s values.

3. inorder(Node* root, vector<int> &arr) Function

• Purpose: Performs an inorder traversal of the input BST to extract all its node values into a vector<int> in sorted ascending order.
• Logic:
  1. Recursively traverse the left subtree.
  2. Add root->data to the arr vector.
  3. Recursively traverse the right subtree.
• Time Complexity: O(N) (visits each node once).
• Space Complexity: O(N) for the arr vector, plus O(H) for recursion stack (H is tree height).

4. fillPreorder(Node* root, int &index, vector<int> arr) Function

• Purpose: Re-populates the nodes of the original tree structure with the sorted values obtained from the inorder traversal. It does this using a pre-order traversal.
• Logic:
  1. Base Case: If root is NULL, return.
  2. Assign Value: If index is within the bounds of arr (meaning there are still sorted values to assign), assign root->data = arr[index++]. This gives the current node the smallest available value.
  3. Recursive Calls: Recursively call fillPreorder for root->left and then root->right.
• How it creates Min Heap Order: By assigning smaller values to parents and progressively larger values to children (due to pre-order traversal and sorted source arr), the parent <= child property is enforced.
• Important Note: This process re-arranges the values within the existing BST structure. It does not guarantee that the resulting tree will be a Complete Binary Tree (CBT), which is a strict requirement for a formal “heap” data structure when implemented in an array. However, the values in the tree will obey the Min Heap property.

5. BST_Heap(Node* root) Function

• Purpose: Orchestrates the entire conversion process.
• Logic:
  1. Creates an empty vector<int> arr.
  2. Calls inorder(root, arr) to fill arr with sorted BST node values.
  3. Initializes an index variable to 0.
  4. Calls fillPreorder(root, index, arr) to re-assign these sorted values back into the BST nodes in pre-order.
• Overall Time Complexity: O(N) (dominated by inorder and fillPreorder).
• Overall Space Complexity: O(N) (for the arr vector).

6. Summary of Transformation

Original BST (sorted in-order): Left -> Root -> Right

Values in arr (sorted): v1, v2, v3, ..., vN

Re-assigned values (pre-order to original structure): Root gets v1 Root->Left gets v2 Root->Left->Left gets v3 (or Root->Right if Root->Left is null), etc.

This assignment pattern guarantees parent <= child property.

---