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. Consider the following Python code snippet for balancing a BST using inorder traversal and iterative construction. Given the BST with nodes 1, 2, 3 inserted in that order, what is the value of the root node after balancing?

easy

A. 1

B. 2

C. 3

D. None (empty tree)

Solution

1. Step 1: Perform inorder traversal on BST with nodes 1, 2, 3

   Inorder traversal yields nodes in sorted order: [1, 2, 3].

2. Step 2: Iteratively build balanced BST choosing middle node

   Middle index is 1 (0-based), so node with value 2 becomes root.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Middle of [1,2,3] is 2 -> root value 2 [OK]

Hint: Middle element of sorted nodes becomes root [OK]

Common Mistakes:

• Choosing left or right middle always, skewing tree
• Confusing preorder with inorder traversal results
• Forgetting to reset left/right pointers causing cycles

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

3. What is the space complexity of the optimal Morris inorder traversal approach used to recover a BST with two swapped nodes, and why might some candidates mistakenly believe it is higher?

medium

A. O(1) because Morris traversal modifies tree pointers temporarily without extra data structures

B. O(n) due to storing node values during traversal

C. O(h) where h is tree height due to recursion stack in inorder traversal

D. O(log n) because of balanced tree height and implicit stack usage

Solution

1. Step 1: Understand Morris traversal space usage

   Morris traversal uses threaded binary tree pointers to traverse without recursion or stack, so no extra space beyond a few pointers.

2. Step 2: Identify common misconception

   Candidates often confuse it with recursive or stack-based inorder traversal, which uses O(h) space, or with storing values in a list, which uses O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal achieves O(1) space by temporarily modifying tree pointers [OK]

Hint: Morris traversal uses threaded pointers, no stack needed [OK]

Common Mistakes:

• Assuming recursion stack space applies
• Confusing storing values with traversal space
• Believing temporary pointer changes increase space

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

5. The following code attempts to search for a value in a BST. Identify the line containing the subtle bug that can cause incorrect behavior or inefficiency.

def searchBST(root, val):
    if root is None:
        return None
    if root.val == val:
        return root
    left_search = searchBST(root.left, val)
    if left_search is not None:
        return left_search
    return searchBST(root.right, val)

medium

A. Line 5: left_search = searchBST(root.left, val)

B. Line 4: if root.val == val: return root

C. Line 2: if root is None: return None

D. Line 7: return searchBST(root.right, val)

Solution

1. Step 1: Understand the code logic

   This code searches both left and right subtrees regardless of BST property.

2. Step 2: Identify inefficiency bug

   Line 5 always searches left subtree even if val > root.val, ignoring BST property and causing O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring BST property causes unnecessary subtree searches [OK]

Hint: Searching both subtrees ignores BST property [OK]

Common Mistakes:

• Not pruning search using BST property