Convert Sorted Array to Balanced BST in DSA C++ - Build from Scratch

Convert Sorted Array to Balanced BST

📖 Scenario: You have a sorted list of numbers representing sorted data. You want to organize this data into a balanced tree structure called a Binary Search Tree (BST). This tree helps you find numbers quickly, like a well-organized phone book.

🎯 Goal: Build a balanced BST from a sorted array of integers. You will create the array, set up helper variables, write the logic to build the tree, and finally print the tree in order.

📋 What You'll Learn

Create a sorted array called nums with the exact values: 1, 2, 3, 4, 5, 6, 7

Create a struct TreeNode with int val, TreeNode* left, and TreeNode* right

Write a function TreeNode* sortedArrayToBST(int left, int right) that builds the balanced BST using recursion

Print the BST values in-order using inorderTraversal(TreeNode* root) to verify the tree structure

💡 Why This Matters

🌍 Real World

Balanced BSTs are used in databases and search engines to quickly find data without scanning everything.

💼 Career

Understanding BSTs and recursion is important for software engineering roles involving data structures and algorithms.

1

Create the sorted array and TreeNode struct

Create a sorted array called nums with these exact values: 1, 2, 3, 4, 5, 6, 7. Also, define a struct called TreeNode with an integer val, and two pointers left and right initialized to nullptr.

DSA C++

// Create the sorted array nums and define TreeNode struct
// Your code here

Hint

Use vector nums = {1, 2, 3, 4, 5, 6, 7}; to create the array. Define TreeNode with val, left, and right members.

2

Add helper function declaration and variables

Declare a function TreeNode* sortedArrayToBST(int left, int right) that will build the BST from the array indices left to right. Also, declare a pointer root of type TreeNode* initialized to nullptr.

DSA C++

#include 
#include 

using namespace std;

vector nums = {1, 2, 3, 4, 5, 6, 7};

struct TreeNode {
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode(int x) : val(x) {}
};

// Declare the function sortedArrayToBST
// Declare TreeNode* root initialized to nullptr
// Your code here

Hint

Write the function declaration for sortedArrayToBST and create a TreeNode* pointer called root set to nullptr.

3

Implement the recursive function to build the BST

Implement the function TreeNode* sortedArrayToBST(int left, int right) that builds the balanced BST recursively. Use the middle element as root, recursively build left subtree from left to mid - 1, and right subtree from mid + 1 to right. Assign the result to root by calling this function with 0 and nums.size() - 1.

DSA C++

#include 
#include 

using namespace std;

vector nums = {1, 2, 3, 4, 5, 6, 7};

struct TreeNode {
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode(int x) : val(x) {}
};

TreeNode* sortedArrayToBST(int left, int right) {
    // Your code here
}

// Assign root by calling sortedArrayToBST with 0 and nums.size() - 1
// Your code here

Hint

Use recursion to pick the middle element as root, build left subtree from left to mid-1, and right subtree from mid+1 to right.

4

Print the BST in-order to verify

Write a function void inorderTraversal(TreeNode* root) that prints the BST values in ascending order by visiting left subtree, root, then right subtree. Then call inorderTraversal(root) to print the values.

DSA C++

#include 
#include 

using namespace std;

vector nums = {1, 2, 3, 4, 5, 6, 7};

struct TreeNode {
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode(int x) : val(x) {}
};

TreeNode* sortedArrayToBST(int left, int right) {
    if (left > right) {
        return nullptr;
    }
    int mid = left + (right - left) / 2;
    TreeNode* node = new TreeNode(nums[mid]);
    node->left = sortedArrayToBST(left, mid - 1);
    node->right = sortedArrayToBST(mid + 1, right);
    return node;
}

int main() {
    TreeNode* root = sortedArrayToBST(0, nums.size() - 1);
    
    // Define inorderTraversal function
    // Call inorderTraversal(root) to print values
    // Your code here
    return 0;
}

Hint

Use recursion to print left subtree, then root value, then right subtree. Call this function with root.