If you're looking to balance an existing Binary Search Tree (BST), you're in luck. We have a straightforward two-step plan to get you there, leveraging the power of arrays and recursion.

Step 1: The Array

In-Order Traversal: A Journey Through the Tree

In this step, we'll be doing an in-order traversal of the BST and store the nodes in an array. This array will serve as the foundation for building a balanced BST.

• C++ STL’s Vector: In C++, we use the vector data structure from the Standard Template Library (STL) for dynamic array handling.

• Python’s List: In Python, we use the built-in list data structure.

Here, we create a convenience function to do the in-order traversal and store the nodes in an array.

1// Convenience function for creating an array from BST in-order traversal
2function createArrayFromTree(root, arr=[]) {
3    if(root === null) return arr;
4    arr = createArrayFromTree(root.left, arr);
5    arr.push(root.val);
6    arr = createArrayFromTree(root.right, arr);
7    return arr;
8}

Step 2: Crafting the Balanced BST

Breaking Down the Pseudocode

Let’s delve into the pseudocode that describes how we can create a balanced BST from a sorted array. The elegance here is in the recursive nature of the problem and the solution.

Base Case: The Simplest Scenario

1. When the Array is Empty: If the array has no elements, return a null pointer.

Recursive Case: Where the Magic Happens

0. Define a Build Method: This is where you'll craft the balanced tree.
1. Find the Middle: Take the middle element of the array and create a root node with it.
2. Craft the Left Subtree: Call build recursively on the left half of the array. The returned pointer becomes the left child of the root.
3. Craft the Right Subtree: Similarly, call build recursively on the right half. The returned pointer becomes the right child of the root.
4. Return the Root: Finally, return the pointer to the root node you created.

Finding the Middle: The Formula

To find the middle of the array, use the formula (size/2). This assumes a zero-based index, typical in most programming languages.