Insert into a BST

🎯

Insert into a BST

easyTREEAmazonGoogle

Imagine you are maintaining a sorted phone directory stored as a binary search tree. When a new contact is added, you need to insert it in the correct position to keep the directory organized.

💡 This problem involves inserting a new value into a Binary Search Tree (BST). Beginners often struggle because they must understand how BST properties guide where to insert the new node, and how recursion or iteration can be used to find the correct spot.

📋

Problem Statement

Given the root node of a binary search tree (BST) and a value to insert into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. The insertion must maintain the BST property.

The number of nodes in the tree is in the range [0, 10^5].-10^8 <= Node.val <= 10^8All the values Node.val are unique.val does not exist in the original BST.

💡

Example

Input"root = [4,2,7,1,3], val = 5"

Output[4,2,7,1,3,5]

Starting at root 4, since 5 > 4, go right to 7. Since 5 < 7, insert 5 as left child of 7.

• Empty tree (root = null) → new node becomes root
• Insert value smaller than all existing nodes → inserted as leftmost leaf
• Insert value larger than all existing nodes → inserted as rightmost leaf
• Insert value between two nodes → inserted as leaf maintaining BST property

⚠️

Common Mistakes

Not updating parent's child pointer after recursion

New node is not linked to the tree, insertion fails silently

✅ Always assign the recursive call result to parent's left or right child

Inserting duplicate values

Violates BST property or infinite recursion

✅ Check if value exists before insertion or rely on problem guarantee

Not handling empty tree (root = null)

Code crashes or returns null instead of new root

✅ Add base case to create new node if root is null

Using incorrect comparison operators (< vs <=)

May insert in wrong subtree, breaking BST property

✅ Use strict less than for left subtree, else right subtree

Forgetting to return root after insertion

Caller receives None or wrong subtree, losing tree structure

✅ Always return root node after insertion

🧠

Brute Force (Recursive Insertion)

💡 This approach uses straightforward recursion to find the correct spot to insert the new value. It is simple and intuitive, helping beginners understand BST traversal and insertion.

Intuition

Start at the root and recursively traverse left or right depending on the value until reaching a null position where the new node can be inserted.

Algorithm

1. If the current node is null, create and return a new node with the value.
2. If the value to insert is less than the current node's value, recursively insert into the left subtree.
3. If the value to insert is greater than the current node's value, recursively insert into the right subtree.
4. Return the current node after insertion to maintain tree connections.

💡 The recursion naturally finds the correct leaf position, but beginners may find it tricky to understand how the tree links are preserved on the way back up.

</>

Code

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

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
    return root

# Driver code to test
if __name__ == '__main__':
    # Construct BST: 4,2,7,1,3
    root = TreeNode(4)
    root.left = TreeNode(2, TreeNode(1), TreeNode(3))
    root.right = TreeNode(7)
    val = 5
    root = insertIntoBST(root, val)
    # Simple inorder traversal to print tree values
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

if root is None:Base case: found the position to insert the new node

return TreeNode(val)Create and return a new node with the given value

if val < root.val:Decide to go left if value is smaller than current node

root.left = insertIntoBST(root.left, val)Recursively insert into left subtree and update link

else:If value is greater, go right

root.right = insertIntoBST(root.right, val)Recursively insert into right subtree and update link

return rootReturn current node to maintain tree structure on recursion unwind

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 static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(7);
        root = sol.insertIntoBST(root, 5);
        printInorder(root);
    }

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

Line Notes

if (root == null) return new TreeNode(val);Base case: insert new node here

if (val < root.val)Traverse left if value is smaller

root.left = insertIntoBST(root.left, val);Recursively insert and update left child

else root.right = insertIntoBST(root.right, val);Otherwise, insert into right subtree

return root;Return current node to maintain tree structure

public static void main(String[] args)Driver code to test insertion and print inorder traversal

#include <iostream>
using namespace std;

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

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;
}

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

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(7);
    root = insertIntoBST(root, 5);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

if (!root) return new TreeNode(val);Base case: insert new node at null position

if (val < root->val)Go left if value is smaller

root->left = insertIntoBST(root->left, val);Recursively insert and update left child pointer

else root->right = insertIntoBST(root->right, val);Otherwise, insert into right subtree

return root;Return current node to maintain tree structure

int main()Driver code to test insertion and print inorder traversal

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

function insertIntoBST(root, 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;
}

// Driver code
const root = new TreeNode(4,
    new TreeNode(2, new TreeNode(1), new TreeNode(3)),
    new TreeNode(7)
);
const newRoot = insertIntoBST(root, 5);

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

Line Notes

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

if (val < root.val)Traverse left if value is smaller

root.left = insertIntoBST(root.left, val);Recursively insert and update left child

else root.right = insertIntoBST(root.right, val);Otherwise, insert into right subtree

return root;Return current node to maintain tree structure

console.log(inorder(newRoot));Print inorder traversal to verify insertion

⏱

Complexity

TimeO(h)

SpaceO(h)

In the worst case, the recursion depth equals the height of the tree h. For a balanced BST, h = O(log n), but for skewed trees, h = O(n).

💡 For n=1000 nodes in a balanced tree, about 10 recursive calls happen; in worst skewed case, up to 1000 calls.

Interview Verdict: Accepted

This approach is efficient enough for balanced trees and is the standard recursive solution for BST insertion.

🧠

Iterative Insertion

💡 This approach avoids recursion by iteratively traversing the tree to find the insertion point, which can be easier to understand for those uncomfortable with recursion and avoids stack overflow.

Intuition

Start at the root and move down the tree iteratively, keeping track of the parent node, until a null child is found where the new node can be inserted.

Algorithm

1. If the tree is empty, create and return a new node as root.
2. Initialize a pointer to traverse the tree and a parent pointer to track the last node.
3. While the current node is not null, update the parent and move left or right depending on the value.
4. Insert the new node as the left or right child of the parent based on the value.

💡 The main challenge is correctly updating the parent's child pointer after traversal without recursion.

</>

Code

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

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    if val < parent.val:
        parent.left = TreeNode(val)
    else:
        parent.right = TreeNode(val)
    return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(4)
    root.left = TreeNode(2, TreeNode(1), TreeNode(3))
    root.right = TreeNode(7)
    val = 5
    root = insertIntoBST(root, val)
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

if root is None:Handle empty tree by creating new root

curr = rootStart traversal from root

parent = NoneKeep track of parent node for insertion

while curr:Traverse until reaching null child

parent = currUpdate parent before moving down

if val < curr.val:Go left if value smaller

curr = curr.leftMove left child

else:Otherwise insert as right child

curr = curr.rightMove right child

if val < parent.val:Insert new node as left child if smaller

parent.left = TreeNode(val)Create new left child

parent.right = TreeNode(val)Create new right child

return rootReturn original root after 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);
        TreeNode curr = root, parent = null;
        while (curr != null) {
            parent = curr;
            if (val < curr.val) curr = curr.left;
            else curr = curr.right;
        }
        if (val < parent.val) parent.left = new TreeNode(val);
        else parent.right = new TreeNode(val);
        return root;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(7);
        root = sol.insertIntoBST(root, 5);
        printInorder(root);
    }

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

Line Notes

if (root == null) return new TreeNode(val);Handle empty tree by creating new root

TreeNode curr = root, parent = null;Initialize traversal and parent pointers

while (curr != null)Traverse until null child found

parent = curr;Update parent before moving down

if (val < curr.val) curr = curr.left;Go left if value smaller

else curr = curr.right;Otherwise go right

if (val < parent.val) parent.left = new TreeNode(val);Insert new node as left child if smaller

else parent.right = new TreeNode(val);Otherwise insert as right child

return root;Return original root after insertion

#include <iostream>
using namespace std;

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

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

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

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(7);
    root = insertIntoBST(root, 5);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

if (!root) return new TreeNode(val);Handle empty tree by creating new root

TreeNode* curr = root;Start traversal from root

TreeNode* parent = nullptr;Keep track of parent node

while (curr)Traverse until null child found

parent = curr;Update parent before moving down

if (val < curr->val) curr = curr->left;Go left if value smaller

else curr = curr->right;Otherwise go right

if (val < parent->val) parent->left = new TreeNode(val);Insert new node as left child

else parent->right = new TreeNode(val);Otherwise insert as right child

return root;Return original root after insertion

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

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

// Driver code
const root = new TreeNode(4,
    new TreeNode(2, new TreeNode(1), new TreeNode(3)),
    new TreeNode(7)
);
const newRoot = insertIntoBST(root, 5);

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

Line Notes

if (root === null) return new TreeNode(val);Handle empty tree by creating new root

let curr = root, parent = null;Initialize traversal and parent pointers

while (curr !== null)Traverse until null child found

parent = curr;Update parent before moving down

if (val < curr.val) curr = curr.left;Go left if value smaller

else curr = curr.right;Otherwise go right

if (val < parent.val) parent.left = new TreeNode(val);Insert new node as left child

else parent.right = new TreeNode(val);Otherwise insert as right child

return root;Return original root after insertion

⏱

Complexity

TimeO(h)

SpaceO(1)

Traversal takes O(h) time where h is tree height. Space is O(1) since no recursion stack is used.

💡 For balanced trees with 1000 nodes, about 10 steps; no extra memory used for recursion.

Interview Verdict: Accepted

Iterative approach is preferred in environments where recursion depth is limited or to avoid stack overhead.

🧠

Morris Insertion (Threaded BST Concept)

💡 This advanced approach uses the idea of threaded binary trees to insert without recursion or stack, by temporarily modifying tree pointers during traversal.

Intuition

Use a pointer to traverse the tree and create temporary threads to predecessors to avoid recursion or stack, inserting the new node when a null child is found.

Algorithm

1. If the tree is empty, create and return a new node as root.
2. Initialize current pointer to root and parent pointer to null.
3. While current is not null, move left or right depending on value, creating temporary threads to predecessors if needed.
4. When a null child is found, insert the new node and break.
5. Restore any modified pointers to maintain original tree structure.

💡 This approach is complex because it temporarily changes tree structure and requires careful pointer management.

</>

Code

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

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    parent = None
    while curr:
        parent = curr
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

# Driver code
if __name__ == '__main__':
    root = TreeNode(4)
    root.left = TreeNode(2, TreeNode(1), TreeNode(3))
    root.right = TreeNode(7)
    val = 5
    root = insertIntoBST(root, val)
    def inorder(node):
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    print(inorder(root))

Line Notes

if root is None:Handle empty tree by creating new root

curr = rootStart traversal from root

parent = NoneTrack parent node for insertion

while curr:Traverse until insertion point found

if val < curr.val:Go left if value smaller

if curr.left is None:If left child null, insert here

curr.left = TreeNode(val)Create new left child node

return rootReturn root after insertion

else:Otherwise go right

if curr.right is None:If right child null, insert here

curr.right = TreeNode(val)Create new right child node

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);
        TreeNode curr = root, parent = null;
        while (curr != null) {
            parent = curr;
            if (val < curr.val) {
                if (curr.left == null) {
                    curr.left = new TreeNode(val);
                    return root;
                }
                curr = curr.left;
            } else {
                if (curr.right == null) {
                    curr.right = new TreeNode(val);
                    return root;
                }
                curr = curr.right;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(7);
        root = sol.insertIntoBST(root, 5);
        printInorder(root);
    }

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

Line Notes

if (root == null) return new TreeNode(val);Handle empty tree by creating new root

TreeNode curr = root, parent = null;Initialize traversal and parent pointers

while (curr != null)Traverse until insertion point found

parent = curr;Update parent before moving down

if (val < curr.val)Go left if value smaller

if (curr.left == null)If left child null, insert here

curr.left = new TreeNode(val);Create new left child node

return root;Return root after insertion

elseOtherwise go right

if (curr.right == null)If right child null, insert here

curr.right = new TreeNode(val);Create new right child node

#include <iostream>
using namespace std;

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

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

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

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(7);
    root = insertIntoBST(root, 5);
    inorder(root);
    cout << endl;
    return 0;
}

Line Notes

if (!root) return new TreeNode(val);Handle empty tree by creating new root

TreeNode* curr = root;Start traversal from root

TreeNode* parent = nullptr;Track parent node

while (curr)Traverse until insertion point found

parent = curr;Update parent before moving down

if (val < curr->val)Go left if value smaller

if (!curr->left)If left child null, insert here

curr->left = new TreeNode(val);Create new left child node

return root;Return root after insertion

elseOtherwise go right

if (!curr->right)If right child null, insert here

curr->right = new TreeNode(val);Create new right child node

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

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

// Driver code
const root = new TreeNode(4,
    new TreeNode(2, new TreeNode(1), new TreeNode(3)),
    new TreeNode(7)
);
const newRoot = insertIntoBST(root, 5);

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

Line Notes

if (root === null) return new TreeNode(val);Handle empty tree by creating new root

let curr = root, parent = null;Initialize traversal and parent pointers

while (curr !== null)Traverse until insertion point found

parent = curr;Update parent before moving down

if (val < curr.val)Go left if value smaller

if (curr.left === null)If left child null, insert here

curr.left = new TreeNode(val);Create new left child node

return root;Return root after insertion

elseOtherwise go right

if (curr.right === null)If right child null, insert here

curr.right = new TreeNode(val);Create new right child node

⏱

Complexity

TimeO(h)

SpaceO(1)

Traversal takes O(h) time where h is tree height. No recursion stack used, so space is O(1).

💡 This approach is similar to iterative but emphasizes pointer manipulation; for balanced trees, about 10 steps for 1000 nodes.

Interview Verdict: Accepted

While more complex, this approach avoids recursion and stack, useful in constrained environments.

📊

All Approaches - One-Glance Tradeoffs

💡 The recursive approach is easiest to implement and understand, so code it in 95% of interviews. Iterative is good if recursion is disallowed. Morris insertion is rarely needed but good to know.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive)	O(h)	O(h) due to recursion stack	Yes (deep recursion in skewed trees)	N/A	Standard approach to code and explain
2. Iterative Insertion	O(h)	O(1)	No	N/A	Good alternative if recursion is restricted
3. Morris Insertion (Threaded BST)	O(h)	O(1)	No	N/A	Mention only; complex to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force recursive approach, followed by iterative and advanced methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive insertion approach.Step 3: Discuss iterative insertion to avoid recursion.Step 4: Optionally mention advanced pointer manipulation methods.Step 5: Code the chosen approach carefully, explaining each step.Step 6: Test with edge cases and explain the results.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of BST properties, recursion or iteration skills, pointer manipulation, and ability to handle edge cases like empty trees.

Common Follow-ups

• How would you delete a node from a BST? → Discuss cases with zero, one, or two children.
• How to balance a BST after insertion? → Mention AVL or Red-Black trees.

💡 These follow-ups test deeper BST knowledge and ability to handle more complex tree operations.

🔍

Pattern Recognition

When to Use

1) You have a BST and need to add a new value. 2) The problem states maintaining BST properties. 3) You must find the correct leaf position. 4) The value is guaranteed unique.

Signature Phrases

insert into BSTmaintain BST propertyvalue does not exist in BST

NOT This Pattern When

Binary tree insertion without BST property (e.g., complete binary tree insertion) is a different pattern.

Similar Problems

Delete Node in a BST - similar traversal and pointer updatesSearch in a BST - similar traversal logicValidate BST - understanding BST properties

Practice

1. You are given a binary search tree and a key. You need to remove the node with this key while maintaining the BST property. Which approach guarantees the correct and efficient deletion in all cases, including nodes with two children?

easy

A. Use a greedy approach that always deletes the node by replacing it with its left child, ignoring the right subtree.

B. Perform a breadth-first traversal to find and remove the node, then rebuild the tree from scratch.

C. Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor.

D. Use dynamic programming to store subtrees and delete nodes based on precomputed results.

Solution

1. Step 1: Understand BST deletion cases

   Deletion must handle three cases: leaf node, node with one child, and node with two children. The two children case requires replacing the node with its in-order successor or predecessor to maintain BST properties.

2. Step 2: Identify approach that handles all cases correctly

   The recursive approach that finds the node, replaces it with its in-order successor if it has two children, and recursively deletes the successor ensures correctness and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor. correctly handles all deletion cases preserving BST [OK]

Hint: Two-children deletion requires successor replacement [OK]

Common Mistakes:

• Greedy deletion ignoring right subtree breaks BST
• Rebuilding tree is inefficient
• Dynamic programming irrelevant here

2. 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

3. You are given a binary tree where each node has a unique integer value. You need to find whether a given value exists in the tree efficiently by leveraging the tree's ordering properties. Which approach guarantees the fastest search in the worst case?

easy

A. Use the BST property to decide whether to search left or right subtree at each node, recursively or iteratively.

B. Perform a breadth-first search (BFS) to find the value level by level.

C. Traverse the entire tree recursively checking each node until the value is found.

D. Use dynamic programming to store previously searched subtrees to avoid repeated work.

Solution

1. Step 1: Understand the problem constraints

   The tree is a BST, so left subtree nodes are less than the node, right subtree nodes are greater.

2. Step 2: Identify the optimal search approach

   Using the BST property allows skipping half of the tree at each step, leading to O(h) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BST property guides search direction efficiently [OK]

Hint: BST property enables directed search, not full traversal [OK]

Common Mistakes:

• Thinking BFS or full traversal is optimal for BST search

4. What is the time complexity of the optimal iterative approach that converts a BST to a Greater Tree using reverse inorder traversal with an explicit stack?

medium

A. O(n) where n is the number of nodes in the BST

B. O(n · h) where n is number of nodes and h is tree height

C. O(n · log n) due to stack operations on balanced BST

D. O(h) where h is the height of the BST because each node is visited once

Solution

1. Step 1: Identify number of nodes visited

   Each node is visited exactly once during traversal.

2. Step 2: Analyze stack operations and overall traversal

   While each node is visited once, the explicit stack can hold up to h nodes, and each push/pop operation can be considered O(1). However, in the worst case (unbalanced tree), the height h can be up to n, making the complexity O(n * h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst-case complexity depends on tree height [OK]

Hint: Worst-case complexity depends on tree height [OK]

Common Mistakes:

• Assuming stack operations multiply complexity by height unnecessarily
• Confusing recursion stack space with time complexity
• Thinking balanced BST implies O(n log n) time

5. Suppose the BST can contain negative values and duplicates, and you want to convert it to a Greater Tree where each node's new value is the sum of all nodes with values greater than or equal to it. Which modification to the optimal iterative approach is necessary to handle duplicates correctly?

hard

A. Change traversal to inorder (left-root-right) to process duplicates in ascending order.

B. Use a hash map to store counts of each value and update nodes after traversal.

C. Skip nodes with duplicate values during traversal to avoid double counting.

D. During traversal, accumulate sum including nodes with values equal to current node before updating node value.

Solution

1. Step 1: Understand how duplicates affect sum accumulation

   Duplicates must be included in the sum for nodes with equal values to maintain correctness.

2. Step 2: Modify accumulation logic

   Accumulate sum including all nodes with values >= current node before updating node.val during reverse inorder traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Including equal values in sum ensures correct Greater Tree with duplicates [OK]

Hint: Include equal values in sum during reverse inorder traversal [OK]

Common Mistakes:

• Changing traversal order breaks sum logic
• Skipping duplicates causes incorrect sums
• Using extra data structures unnecessarily increases complexity