Convert Sorted Array to Height-Balanced BST

🎯

Convert Sorted Array to Height-Balanced BST

easyTREEAmazonGoogleFacebook

Imagine you have a sorted list of book IDs and want to organize them in a way that allows quick search and insertion. Creating a balanced binary search tree from this sorted list ensures efficient operations.

💡 This problem is about constructing a balanced binary search tree (BST) from a sorted array. Beginners often struggle because they try to insert elements one by one, which leads to unbalanced trees. Understanding how to pick the middle element as root to maintain balance is key.

📋

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is sorted in ascending order

💡

Example

Input"nums = [-10, -3, 0, 5, 9]"

Output[0, -3, 9, -10, null, 5]

Choosing 0 as root splits array into left [-10, -3] and right [5, 9]. Recursively building subtrees results in a balanced BST. Note: This output is a level order traversal with nulls for missing nodes. In test cases, inorder traversal arrays are used to verify correctness.

• Single element array → tree with one node
• Two elements array → root and one child
• All elements are the same → balanced tree with duplicates allowed
• Large array with 10^5 elements → performance and stack depth considerations

⚠️

Common Mistakes

Inserting elements one by one from sorted array

Creates skewed tree, leading to O(n^2) time and unbalanced BST

✅ Use divide and conquer to pick middle element as root

Incorrect mid calculation causing infinite recursion

Stack overflow or infinite loop

✅ Calculate mid as (left + right) // 2 or left + (right - left) // 2

Not handling base case left > right properly

Recursion never ends or returns wrong subtree

✅ Return null when left > right

Using array slicing in recursion

Extra O(n) space and time overhead per call, inefficient for large inputs

✅ Use indices to pass subarray boundaries instead of slicing

Mixing up left and right subtree indices

Incorrect tree structure, failing balance or BST property

✅ Carefully assign left subtree to left..mid-1 and right subtree to mid+1..right

🧠

Brute Force (Insert One by One)

💡 This approach exists to show the naive way of building a BST by inserting elements one by one, which is intuitive but inefficient and leads to unbalanced trees.

Intuition

Insert each element from the sorted array into the BST in order. Since the array is sorted, inserting sequentially creates a skewed tree.

Algorithm

1. Initialize an empty BST.
2. Iterate over each element in the sorted array.
3. Insert the current element into the BST using standard BST insertion.
4. Return the root of the BST after all insertions.

💡 The difficulty is realizing that inserting sorted elements sequentially creates a skewed tree, not balanced.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

def sorted_array_to_bst(nums):
    root = None
    for num in nums:
        root = insert_into_bst(root, num)
    return root

# Driver code to test
if __name__ == '__main__':
    nums = [-10, -3, 0, 5, 9]
    root = sorted_array_to_bst(nums)
    # Simple inorder traversal to print sorted values
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

class TreeNode:Defines the structure of a BST node with value and left/right children

def insert_into_bst(root, val):Defines recursive insertion function for BST

if not root:Base case: insert new node when reaching null position

if val < root.val:Decide to go left or right based on BST property

root.left = insert_into_bst(root.left, val)Recursively insert in left subtree

for num in nums:Iterate over all elements to insert sequentially

root = insert_into_bst(root, num)Update root after each insertion

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val < root.val) root.left = insertIntoBST(root.left, val);
        else root.right = insertIntoBST(root.right, val);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = null;
        for (int num : nums) {
            root = insertIntoBST(root, num);
        }
        return root;
    }

    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sol.sortedArrayToBST(nums);
        inorder(root);
    }
}

Line Notes

class TreeNode {Defines BST node structure with value and children

public TreeNode insertIntoBST(TreeNode root, int val) {Recursive insertion method for BST

if (root == null) return new TreeNode(val);Base case: create new node when null reached

if (val < root.val) root.left = insertIntoBST(root.left, val);Insert into left subtree if smaller

for (int num : nums) {Iterate over all elements to insert sequentially

root = insertIntoBST(root, num);Update root after each insertion

public static void main(String[] args) {Driver code entry point

#include <iostream>
#include <vector>
using namespace std;

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

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insertIntoBST(root->left, val);
    else root->right = insertIntoBST(root->right, val);
    return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = nullptr;
    for (int num : nums) {
        root = insertIntoBST(root, num);
    }
    return root;
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode* root = sortedArrayToBST(nums);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

struct TreeNode {Defines BST node with value and pointers to children

TreeNode* insertIntoBST(TreeNode* root, int val) {Recursive insertion function for BST

if (!root) return new TreeNode(val);Create new node when null reached

if (val < root->val) root->left = insertIntoBST(root->left, val);Insert into left subtree if smaller

for (int num : nums) {Iterate over all elements to insert sequentially

root = insertIntoBST(root, num);Update root after each insertion

int main() {Driver code entry point

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function insertIntoBST(root, val) {
    if (!root) return new TreeNode(val);
    if (val < root.val) root.left = insertIntoBST(root.left, val);
    else root.right = insertIntoBST(root.right, val);
    return root;
}

function sortedArrayToBST(nums) {
    let root = null;
    for (const num of nums) {
        root = insertIntoBST(root, num);
    }
    return root;
}

// Driver code
const nums = [-10, -3, 0, 5, 9];
const root = sortedArrayToBST(nums);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(root));

Line Notes

class TreeNode {Defines BST node with value and left/right children

function insertIntoBST(root, val) {Recursive insertion function for BST

if (!root) return new TreeNode(val);Create new node when null reached

if (val < root.val) root.left = insertIntoBST(root.left, val);Insert into left subtree if smaller

for (const num of nums) {Iterate over all elements to insert sequentially

root = insertIntoBST(root, num);Update root after each insertion

console.log(inorder(root));Print inorder traversal to verify BST

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Each insertion takes O(h) time, where h is tree height. Since tree becomes skewed, h can be O(n), so total O(n^2).

💡 For n=20, this means roughly 400 operations, which is inefficient for large inputs.

Interview Verdict: Accepted but inefficient

This approach works but is too slow for large inputs and produces unbalanced trees, so better methods are preferred.

🧠

Better (Divide and Conquer Recursion)

💡 This approach uses the sorted property to pick the middle element as root, ensuring balance. It introduces recursion to build subtrees efficiently.

Intuition

Pick the middle element of the current subarray as root, recursively build left subtree from left half and right subtree from right half.

Algorithm

1. Define a recursive function that takes left and right indices of the current subarray.
2. If left > right, return null (base case).
3. Find mid = (left + right) // 2, create a node with nums[mid].
4. Recursively build left subtree from left to mid-1 and right subtree from mid+1 to right.
5. Return the node.

💡 The recursion and indices can be tricky at first, but it directly uses the sorted order to maintain balance.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def helper(nums, left, right):
    if left > right:
        return None
    mid = (left + right) // 2
    root = TreeNode(nums[mid])
    root.left = helper(nums, left, mid - 1)
    root.right = helper(nums, mid + 1, right)
    return root

def sorted_array_to_bst(nums):
    return helper(nums, 0, len(nums) - 1)

# Driver code
if __name__ == '__main__':
    nums = [-10, -3, 0, 5, 9]
    root = sorted_array_to_bst(nums)
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

class TreeNode:Defines the BST node structure with value and children

def helper(nums, left, right):Recursive helper to build BST from subarray

if left > right:Base case: no elements to process

mid = (left + right) // 2Pick middle element to maintain balance

root = TreeNode(nums[mid])Create node with middle element as root

root.left = helper(nums, left, mid - 1)Build left subtree recursively

root.right = helper(nums, mid + 1, right)Build right subtree recursively

return rootReturn constructed subtree root

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sol.sortedArrayToBST(nums);
        inorder(root);
    }
}

Line Notes

class TreeNode {Defines BST node structure

public TreeNode helper(int[] nums, int left, int right) {Recursive helper to build BST from subarray

if (left > right) return null;Base case: no elements left

int mid = left + (right - left) / 2;Calculate middle index safely

TreeNode root = new TreeNode(nums[mid]);Create node with middle element as root

root.left = helper(nums, left, mid - 1);Build left subtree recursively

root.right = helper(nums, mid + 1, right);Build right subtree recursively

return root;Return constructed subtree root

#include <iostream>
#include <vector>
using namespace std;

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

TreeNode* helper(const vector<int>& nums, int left, int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = helper(nums, left, mid - 1);
    root->right = helper(nums, mid + 1, right);
    return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode* root = sortedArrayToBST(nums);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

struct TreeNode {Defines BST node structure

TreeNode* helper(const vector<int>& nums, int left, int right) {Recursive helper to build BST from subarray

if (left > right) return nullptr;Base case: no elements left

int mid = left + (right - left) / 2;Calculate middle index safely

TreeNode* root = new TreeNode(nums[mid]);Create node with middle element as root

root->left = helper(nums, left, mid - 1);Build left subtree recursively

root->right = helper(nums, mid + 1, right);Build right subtree recursively

return root;Return constructed subtree root

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function helper(nums, left, right) {
    if (left > right) return null;
    const mid = Math.floor((left + right) / 2);
    const root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
}

function sortedArrayToBST(nums) {
    return helper(nums, 0, nums.length - 1);
}

// Driver code
const nums = [-10, -3, 0, 5, 9];
const root = sortedArrayToBST(nums);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(root));

Line Notes

class TreeNode {Defines BST node structure

function helper(nums, left, right) {Recursive helper to build BST from subarray

if (left > right) return null;Base case: no elements left

const mid = Math.floor((left + right) / 2);Calculate middle index safely

const root = new TreeNode(nums[mid]);Create node with middle element as root

root.left = helper(nums, left, mid - 1);Build left subtree recursively

root.right = helper(nums, mid + 1, right);Build right subtree recursively

return root;Return constructed subtree root

⏱

Complexity

TimeO(n)

SpaceO(log n)

Each element is visited once to create nodes. Recursion stack depth is O(log n) due to balanced splits.

💡 For n=20, this means about 20 operations and recursion depth about 4-5, which is efficient.

Interview Verdict: Accepted and efficient

This is the standard and optimal approach for this problem, balancing simplicity and performance.

🧠

Optimal (Inorder Simulation with Index Pointer)

💡 This approach simulates inorder traversal to build the BST in O(n) time without slicing arrays, improving space efficiency.

Intuition

Use recursion to build left subtree of size n/2, then create root from middle element, then build right subtree. This simulates inorder traversal.

Algorithm

1. Maintain a global or external index pointer starting at 0.
2. Recursively build left subtree from left to mid-1.
3. Create root node with nums[mid].
4. Increment index pointer.
5. Recursively build right subtree from mid+1 to right.
6. Return root node.

💡 This approach avoids slicing arrays, which can be costly, by using index pointers and simulating inorder traversal.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.index = 0

    def helper(self, nums, left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        left_child = self.helper(nums, left, mid - 1)
        root = TreeNode(nums[mid])
        self.index += 1
        root.left = left_child
        root.right = self.helper(nums, mid + 1, right)
        return root

    def sorted_array_to_bst(self, nums):
        self.index = 0
        return self.helper(nums, 0, len(nums) - 1)

# Driver code
if __name__ == '__main__':
    nums = [-10, -3, 0, 5, 9]
    sol = Solution()
    root = sol.sorted_array_to_bst(nums)
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

class TreeNode:Defines BST node structure

class Solution:Encapsulates index pointer and helper method

self.index = 0Reset index before recursion

def helper(self, nums, left, right):Recursive helper to build BST simulating inorder traversal

if left > right:Base case: no elements left

mid = (left + right) // 2Calculate middle index

left_child = self.helper(nums, left, mid - 1)Build left subtree first to simulate inorder

root = TreeNode(nums[mid])Create root node from middle element to maintain BST property

self.index += 1Increment index pointer after using element

root.left = left_childAssign left subtree

root.right = self.helper(nums, mid + 1, right)Build right subtree after root

return rootReturn constructed subtree root

def sorted_array_to_bst(self, nums):Entry function to start recursion

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    int index = 0;

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode leftChild = helper(nums, left, mid - 1);
        TreeNode root = new TreeNode(nums[mid]);
        index++;
        root.left = leftChild;
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        index = 0;
        return helper(nums, 0, nums.length - 1);
    }

    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sol.sortedArrayToBST(nums);
        inorder(root);
    }
}

Line Notes

class TreeNode {Defines BST node structure

int index = 0;Index pointer to track current element

public TreeNode helper(int[] nums, int left, int right) {Recursive helper simulating inorder traversal

if (left > right) return null;Base case: no elements left

int mid = (left + right) / 2;Calculate middle index

TreeNode leftChild = helper(nums, left, mid - 1);Build left subtree first

TreeNode root = new TreeNode(nums[mid]);Create root node from middle element

index++;Increment index after using element

root.left = leftChild;Assign left subtree

root.right = helper(nums, mid + 1, right);Build right subtree after root

return root;Return constructed subtree root

public TreeNode sortedArrayToBST(int[] nums) {Entry function to start recursion

index = 0;Reset index before recursion

#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    int index = 0;

    TreeNode* helper(const vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* leftChild = helper(nums, left, mid - 1);
        TreeNode* root = new TreeNode(nums[mid]);
        index++;
        root->left = leftChild;
        root->right = helper(nums, mid + 1, right);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        index = 0;
        return helper(nums, 0, nums.size() - 1);
    }
};

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    vector<int> nums = {-10, -3, 0, 5, 9};
    Solution sol;
    TreeNode* root = sol.sortedArrayToBST(nums);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

struct TreeNode {Defines BST node structure

int index = 0;Index pointer to track current element

TreeNode* helper(const vector<int>& nums, int left, int right) {Recursive helper simulating inorder traversal

if (left > right) return nullptr;Base case: no elements left

int mid = (left + right) / 2;Calculate middle index

TreeNode* leftChild = helper(nums, left, mid - 1);Build left subtree first

TreeNode* root = new TreeNode(nums[mid]);Create root node from middle element

index++;Increment index after using element

root->left = leftChild;Assign left subtree

root->right = helper(nums, mid + 1, right);Build right subtree after root

return root;Return constructed subtree root

TreeNode* sortedArrayToBST(vector<int>& nums) {Entry function to start recursion

index = 0;Reset index before recursion

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    constructor() {
        this.index = 0;
    }

    helper(nums, left, right) {
        if (left > right) return null;
        const mid = Math.floor((left + right) / 2);
        const leftChild = this.helper(nums, left, mid - 1);
        const root = new TreeNode(nums[mid]);
        this.index++;
        root.left = leftChild;
        root.right = this.helper(nums, mid + 1, right);
        return root;
    }

    sortedArrayToBST(nums) {
        this.index = 0;
        return this.helper(nums, 0, nums.length - 1);
    }
}

// Driver code
const nums = [-10, -3, 0, 5, 9];
const sol = new Solution();
const root = sol.sortedArrayToBST(nums);

function inorder(node) {
    if (!node) return [];
    return [...inorder(node.left), node.val, ...inorder(node.right)];
}

console.log(inorder(root));

Line Notes

class TreeNode {Defines BST node structure

constructor() {Initialize index pointer

this.index = 0;Reset index before recursion

helper(nums, left, right) {Recursive helper simulating inorder traversal

if (left > right) return null;Base case: no elements left

const mid = Math.floor((left + right) / 2);Calculate middle index

const leftChild = this.helper(nums, left, mid - 1);Build left subtree first

const root = new TreeNode(nums[mid]);Create root node from middle element

this.index++;Increment index after using element

root.left = leftChild;Assign left subtree

root.right = this.helper(nums, mid + 1, right);Build right subtree after root

return root;Return constructed subtree root

⏱

Complexity

TimeO(n)

SpaceO(log n)

Each element is processed once. Recursion stack depth is O(log n) due to balanced tree construction.

💡 For n=20, about 20 operations and recursion depth 4-5, efficient and minimal overhead.

Interview Verdict: Accepted and optimal

This approach is optimal in time and space, especially for large inputs, and avoids extra array slicing.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the divide and conquer recursive approach (Approach 2) is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Insert One by One)	O(n^2)	O(n)	Yes (deep recursion if skewed)	Yes	Mention only - never code
2. Divide and Conquer Recursion	O(n)	O(log n)	No (balanced recursion depth)	Yes	Code this approach in most interviews
3. Inorder Simulation with Index Pointer	O(n)	O(log n)	No	Yes	Use for large inputs or when avoiding slicing

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimal solution with code.

How to Present

Clarify the problem and constraints.Describe the brute force approach of inserting elements one by one and its drawbacks.Introduce the divide and conquer recursive approach using the middle element.Explain the optimal inorder simulation approach to avoid extra space.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of BST properties, recursion, balanced tree construction, and ability to optimize naive solutions.

Common Follow-ups

• What if the input is a linked list instead of an array? → Use slow/fast pointers to find middle.
• How to validate if a tree is height-balanced? → Check height difference recursively.

💡 These follow-ups test your ability to adapt the solution to related problems and understand tree properties.

🔍

Pattern Recognition

When to Use

1) Input is sorted array or list, 2) Need to build BST, 3) Balanced tree required, 4) Recursive divide and conquer fits

Signature Phrases

sorted arrayheight-balanced binary search treemiddle element as root

NOT This Pattern When

Building BST from unsorted array (requires sorting or different approach)

Similar Problems

Convert Sorted List to BST - similar but input is linked listValidate BST - checks BST property, related to tree correctness

Practice

1. You are given a binary search tree and two integers low and high. You need to find the sum of all node values within the range [low, high]. Which approach guarantees the most efficient traversal by leveraging the BST properties?

easy

A. Traverse all nodes in the tree and sum those within the range, ignoring BST properties.

B. Perform a depth-first search with pruning: skip left subtree if node value is less than low, skip right subtree if node value is greater than high.

C. Use dynamic programming to store sums of subtrees and combine results for the range query.

D. Apply a breadth-first search (BFS) to visit nodes level by level and sum values within the range.

Solution

1. Step 1: Understand BST property for pruning

   In a BST, left subtree nodes are smaller and right subtree nodes are larger than the current node. This allows skipping entire subtrees outside the range.

2. Step 2: Choose DFS with pruning

   DFS with pruning visits only nodes that could fall within [low, high], avoiding unnecessary traversal and improving efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pruning reduces nodes visited compared to full traversal [OK]

Hint: BST pruning skips irrelevant subtrees [OK]

Common Mistakes:

• Ignoring BST properties leads to full traversal
• Using BFS misses pruning advantage

2. Consider the following code snippet for searching a value in a BST. What will be printed when searching for the value 3 in the given tree?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def searchBST(root, val):
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
result = searchBST(root, 3)
print(result.val if result else 'null')

easy

A. 2

B. 7

C. null

D. 3

Solution

1. Step 1: Trace the search path

   Start at root (4). Since 3 < 4, move to left child (2). Since 3 > 2, move to right child (3).

2. Step 2: Check node value

   Current node value is 3, which matches the search value, so return this node.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Search follows BST property correctly and finds node with value 3 [OK]

Hint: Follow BST property to move left or right [OK]

Common Mistakes:

• Returning wrong node value due to off-by-one traversal

3. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

A. O(n log n) due to sorting nodes during traversal

B. O(n) because inorder traversal and balanced rebuild each take linear time

C. O(n^2) because rebuilding the tree involves repeated subtree constructions

D. O(n) for traversal but O(n log n) for balanced tree construction

Solution

1. Step 1: Analyze inorder traversal time

   Inorder traversal visits each node once -> O(n).

2. Step 2: Analyze balanced BST construction time

   Rebuilding uses indices to pick middle nodes without extra sorting -> O(n).

3. Step 3: Consider sorting complexity

   Although inorder traversal produces sorted nodes, if sorting is mistakenly applied, complexity becomes O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting nodes during traversal leads to O(n log n) [Trap]

Hint: Beware of sorting overhead; if sorting is done, complexity is O(n log n)

Common Mistakes:

• Assuming sorting is not needed, leading to O(n)
• Thinking recursive rebuild is O(n^2) due to repeated subtree calls
• Confusing traversal and construction complexities

4. What is the time complexity of the iterative inorder traversal approach to find the kth smallest element in a BST, where H is the height of the tree and k is the input parameter?

medium

A. O(H + k), where H is the height of the tree and k is the kth element to find

B. O(k), since only k nodes are visited

C. O(k log n), assuming balanced BST

D. O(n), where n is the total number of nodes in the BST

Solution

1. Step 1: Analyze traversal steps

   The algorithm traverses down to the leftmost node (cost O(H)) and then visits k nodes in inorder sequence.

2. Step 2: Combine costs

   Total time is O(H) to reach leftmost node plus O(k) to visit k nodes, so O(H + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal cost depends on height plus k nodes visited [OK]

Hint: Traversal cost includes height plus k nodes visited [OK]

Common Mistakes:

• Assuming O(n) always
• Ignoring height cost
• Assuming only k nodes visited without stack overhead

5. What is the worst-case time complexity of the optimal iterative BST search algorithm when searching for a value in a BST with n nodes and height h?

medium

A. O(log n) always because BSTs are balanced.

B. O(n) because you might have to visit every node in the tree.

C. O(h) because the search path follows the height of the tree.

D. O(1) because the search uses direct indexing.

Solution

1. Step 1: Understand BST height and search path

   The search path length is at most the height h of the BST, as each step moves down one level.

2. Step 2: Analyze worst-case time complexity

   In worst case (unbalanced tree), h can be up to n, but complexity is expressed as O(h), not O(n) directly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search complexity depends on tree height, not total nodes necessarily [OK]

Hint: Time depends on tree height, not total nodes always [OK]

Common Mistakes:

• Assuming O(log n) always, ignoring unbalanced trees