Delete Node in a BST

🎯

Delete Node in a BST

mediumTREEAmazonGoogleFacebook

Imagine managing a dynamic directory of contacts where you need to remove entries efficiently while maintaining sorted order for quick lookup.

💡 Deleting a node in a BST is tricky because you must maintain the BST property after removal. Beginners often struggle with handling the three distinct cases of deletion and correctly finding the inorder successor or predecessor.

📋

Problem Statement

Given the root of a binary search tree (BST) and a key, delete the node with the given key in the BST. Return the root node of the BST after deletion. The deletion must maintain the BST property.

The number of nodes in the tree is in the range [1, 10^5].Node values are unique.The key is guaranteed to be in the BST.

💡

Example

Input"root = [5,3,6,2,4,null,7], key = 3"

Output[5,4,6,2,null,null,7]

Node 3 has two children. Replace it with its inorder successor 4, then delete node 4.

• Deleting a leaf node → simply remove it
• Deleting a node with only one child → replace node with child
• Deleting the root node → tree root changes
• Deleting a node not present → tree remains unchanged

⚠️

Common Mistakes

Not handling the two children case correctly

BST property breaks or incorrect node deleted

✅ Always replace with inorder successor or predecessor and delete that node recursively

Forgetting to update parent's child pointer in iterative approach

Deleted node remains linked, causing incorrect tree structure

✅ Track parent node and update its left or right pointer accordingly

Returning wrong subtree when deleting root node

Tree root becomes null or incorrect node

✅ Check if parent is null and return child as new root

Not handling empty tree or key not found

Null pointer exceptions or infinite loops

✅ Add base case checks for null root and return original tree if key not found

🧠

Brute Force (Recursive Search and Delete)

💡 This approach introduces the fundamental recursive logic to find and delete nodes in BST. It helps beginners understand the problem structure before optimizing.

Intuition

Recursively search for the node to delete. Once found, handle three cases: leaf node, node with one child, and node with two children by replacing with inorder successor.

Algorithm

1. If root is null, return null.
2. If key is less than root's value, recurse on left subtree.
3. If key is greater than root's value, recurse on right subtree.
4. If key equals root's value, handle deletion:
5. - If node is leaf, return null.
6. - If node has one child, return that child.
7. - If node has two children, find inorder successor, replace node's value, and delete successor recursively.

💡 The challenge is to carefully handle each deletion case and maintain BST properties during recursion.

</>

Code

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

def deleteNode(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            successor = root.right
            while successor.left:
                successor = successor.left
            root.val = successor.val
            root.right = deleteNode(root.right, successor.val)
    return root

# Example usage:
# Construct BST and call deleteNode(root, key)

Line Notes

if not root:Base case: if tree/subtree is empty, nothing to delete

if key < root.val:Search left subtree if key is smaller

elif key > root.val:Search right subtree if key is larger

else:Found node to delete

if not root.left:If no left child, replace node with right child

elif not root.right:If no right child, replace node with left child

successor = root.rightFind inorder successor in right subtree

while successor.left:Go as left as possible to find smallest node

root.val = successor.valReplace current node's value with successor's value

root.right = deleteNode(root.right, successor.val)Delete successor node recursively

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

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode successor = root.right;
                while (successor.left != null) successor = successor.left;
                root.val = successor.val;
                root.right = deleteNode(root.right, successor.val);
            }
        }
        return root;
    }

    // Example main method to test
    public static void main(String[] args) {
        // Build BST and call deleteNode
    }
}

Line Notes

if (root == null) return null;Base case: empty subtree

if (key < root.val)Traverse left subtree if key smaller

else if (key > root.val)Traverse right subtree if key larger

else {Found node to delete

if (root.left == null) return root.right;No left child, replace with right

else if (root.right == null) return root.left;No right child, replace with left

TreeNode successor = root.right;Find inorder successor

while (successor.left != null) successor = successor.left;Go left to find smallest node

root.val = successor.val;Replace value with successor's

root.right = deleteNode(root.right, successor.val);Delete successor recursively

#include <iostream>
using namespace std;

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

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return NULL;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) return root->right;
        else if (!root->right) return root->left;
        else {
            TreeNode* successor = root->right;
            while (successor->left) successor = successor->left;
            root->val = successor->val;
            root->right = deleteNode(root->right, successor->val);
        }
    }
    return root;
}

// Example usage in main
int main() {
    // Build BST and call deleteNode
    return 0;
}

Line Notes

if (!root) return NULL;Base case: empty subtree

if (key < root->val)Traverse left subtree if key smaller

else if (key > root->val)Traverse right subtree if key larger

else {Found node to delete

if (!root->left) return root->right;No left child, replace with right

else if (!root->right) return root->left;No right child, replace with left

TreeNode* successor = root->right;Find inorder successor

while (successor->left) successor = successor->left;Go left to find smallest node

root->val = successor->val;Replace value with successor's

root->right = deleteNode(root->right, successor->val);Delete successor recursively

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

function deleteNode(root, key) {
    if (!root) return null;
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (!root.left) return root.right;
        else if (!root.right) return root.left;
        else {
            let successor = root.right;
            while (successor.left) successor = successor.left;
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
    }
    return root;
}

// Example usage:
// let root = new TreeNode(...);
// console.log(deleteNode(root, key));

Line Notes

if (!root) return null;Base case: empty subtree

if (key < root.val)Traverse left subtree if key smaller

else if (key > root.val)Traverse right subtree if key larger

else {Found node to delete

if (!root.left) return root.right;No left child, replace with right

else if (!root.right) return root.left;No right child, replace with left

let successor = root.right;Find inorder successor

while (successor.left) successor = successor.left;Go left to find smallest node

root.val = successor.val;Replace value with successor's

root.right = deleteNode(root.right, successor.val);Delete successor recursively

⏱

Complexity

TimeO(h) where h is the height of the BST

SpaceO(h) due to recursion stack

We traverse down the tree once to find the node, which takes O(h). Deletion and successor search also take O(h) in worst case.

💡 For a balanced BST with n=10^5, height h ~ 17, so about 17 recursive calls and operations.

Interview Verdict: Accepted

This approach is efficient for balanced BSTs and is the standard recursive solution interviewers expect.

🧠

Iterative Approach with Parent Pointers

💡 This approach avoids recursion by iteratively searching for the node and its parent, which can be easier to understand and avoids stack overflow.

Intuition

Use a loop to find the node and its parent. Then handle deletion cases by adjusting pointers iteratively.

Algorithm

1. Initialize parent and current pointers starting at root.
2. Iteratively search for the node with the key, updating parent.
3. If node not found, return original root.
4. If node has two children, find inorder successor and its parent.
5. Replace node's value with successor's value.
6. Delete successor node by adjusting parent's child pointer.
7. If node has one or zero children, replace node with child directly.
8. Return updated root.

💡 Tracking parents explicitly helps re-link nodes without recursion, but 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 deleteNode(root, key):
    parent = None
    curr = root
    # Find node to delete
    while curr and curr.val != key:
        parent = curr
        if key < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    if not curr:
        return root
    # Node with two children
    if curr.left and curr.right:
        succ_parent = curr
        succ = curr.right
        while succ.left:
            succ_parent = succ
            succ = succ.left
        curr.val = succ.val
        curr = succ
        parent = succ_parent
    # Node with zero or one child
    child = curr.left if curr.left else curr.right
    if not parent:
        return child
    if parent.left == curr:
        parent.left = child
    else:
        parent.right = child
    return root

# Example usage:
# Construct BST and call deleteNode(root, key)

Line Notes

parent = NoneInitialize parent pointer to track node's parent

while curr and curr.val != key:Iteratively search for node with key

if not curr:If node not found, return original tree

if curr.left and curr.right:If node has two children, find inorder successor

while succ.left:Find leftmost node in right subtree

curr.val = succ.valReplace node's value with successor's

child = curr.left if curr.left else curr.rightIdentify child to replace node

if not parent:If deleting root, return child as new root

if parent.left == curr:Update parent's left or right pointer accordingly

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

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode parent = null, curr = root;
        while (curr != null && curr.val != key) {
            parent = curr;
            if (key < curr.val) curr = curr.left;
            else curr = curr.right;
        }
        if (curr == null) return root;
        if (curr.left != null && curr.right != null) {
            TreeNode succParent = curr;
            TreeNode succ = curr.right;
            while (succ.left != null) {
                succParent = succ;
                succ = succ.left;
            }
            curr.val = succ.val;
            curr = succ;
            parent = succParent;
        }
        TreeNode child = (curr.left != null) ? curr.left : curr.right;
        if (parent == null) return child;
        if (parent.left == curr) parent.left = child;
        else parent.right = child;
        return root;
    }

    // main method omitted for brevity
}

Line Notes

TreeNode parent = null, curr = root;Initialize pointers to track current node and its parent

while (curr != null && curr.val != key)Iteratively find node to delete

if (curr == null) return root;If node not found, return original tree

if (curr.left != null && curr.right != null)If node has two children, find inorder successor

while (succ.left != null)Find leftmost node in right subtree

curr.val = succ.val;Replace node's value with successor's

TreeNode child = (curr.left != null) ? curr.left : curr.right;Identify child to replace node

if (parent == null) return child;If deleting root, return child as new root

if (parent.left == curr) parent.left = child;Update parent's pointer to bypass deleted node

#include <iostream>
using namespace std;

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

TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode* parent = NULL;
    TreeNode* curr = root;
    while (curr && curr->val != key) {
        parent = curr;
        if (key < curr->val) curr = curr->left;
        else curr = curr->right;
    }
    if (!curr) return root;
    if (curr->left && curr->right) {
        TreeNode* succParent = curr;
        TreeNode* succ = curr->right;
        while (succ->left) {
            succParent = succ;
            succ = succ->left;
        }
        curr->val = succ->val;
        curr = succ;
        parent = succParent;
    }
    TreeNode* child = curr->left ? curr->left : curr->right;
    if (!parent) return child;
    if (parent->left == curr) parent->left = child;
    else parent->right = child;
    return root;
}

int main() {
    // Build BST and call deleteNode
    return 0;
}

Line Notes

TreeNode* parent = NULL;Track parent node for re-linking

while (curr && curr->val != key)Iteratively find node to delete

if (!curr) return root;If node not found, return original tree

if (curr->left && curr->right)If node has two children, find inorder successor

while (succ->left)Find leftmost node in right subtree

curr->val = succ->val;Replace node's value with successor's

TreeNode* child = curr->left ? curr->left : curr->right;Identify child to replace node

if (!parent) return child;If deleting root, return child as new root

if (parent->left == curr) parent->left = child;Update parent's pointer to bypass deleted node

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

function deleteNode(root, key) {
    let parent = null, curr = root;
    while (curr && curr.val !== key) {
        parent = curr;
        if (key < curr.val) curr = curr.left;
        else curr = curr.right;
    }
    if (!curr) return root;
    if (curr.left && curr.right) {
        let succParent = curr;
        let succ = curr.right;
        while (succ.left) {
            succParent = succ;
            succ = succ.left;
        }
        curr.val = succ.val;
        curr = succ;
        parent = succParent;
    }
    let child = curr.left ? curr.left : curr.right;
    if (!parent) return child;
    if (parent.left === curr) parent.left = child;
    else parent.right = child;
    return root;
}

// Example usage:
// let root = new TreeNode(...);
// console.log(deleteNode(root, key));

Line Notes

let parent = null, curr = root;Initialize pointers to track current node and parent

while (curr && curr.val !== key)Iteratively find node to delete

if (!curr) return root;If node not found, return original tree

if (curr.left && curr.right)If node has two children, find inorder successor

while (succ.left)Find leftmost node in right subtree

curr.val = succ.val;Replace node's value with successor's

let child = curr.left ? curr.left : curr.right;Identify child to replace node

if (!parent) return child;If deleting root, return child as new root

if (parent.left === curr) parent.left = child;Update parent's pointer to bypass deleted node

⏱

Complexity

TimeO(h) where h is the height of the BST

SpaceO(1) iterative approach uses constant extra space

We traverse the tree once to find the node and possibly its successor, both O(h). No recursion stack is used.

💡 For balanced BSTs with height ~17 for n=10^5, this means about 17 steps without recursion overhead.

Interview Verdict: Accepted

This approach is preferred when recursion depth is a concern and demonstrates pointer manipulation skills.

🧠

Optimized Recursive with Helper Function for Successor

💡 This approach modularizes the code by extracting successor finding into a helper, improving readability and maintainability.

Intuition

Use recursion for deletion and a helper function to find the inorder successor, making the main function cleaner and easier to understand.

Algorithm

1. If root is null, return null.
2. Recursively search left or right subtree based on key.
3. If node to delete found:
4. - If no left child, return right child.
5. - If no right child, return left child.
6. - Otherwise, find inorder successor using helper, replace node's value, and delete successor recursively.
7. Return root.

💡 Separating successor logic helps avoid clutter and makes debugging easier.

</>

Code

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

def findSuccessor(node):
    curr = node.right
    while curr.left:
        curr = curr.left
    return curr

def deleteNode(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            successor = findSuccessor(root)
            root.val = successor.val
            root.right = deleteNode(root.right, successor.val)
    return root

# Example usage:
# Construct BST and call deleteNode(root, key)

Line Notes

def findSuccessor(node):Helper function to find inorder successor

curr = node.rightStart from right child to find successor

while curr.left:Go left as far as possible

if key < root.val:Recurse left if key smaller

elif key > root.val:Recurse right if key larger

if not root.left:No left child, replace with right

elif not root.right:No right child, replace with left

successor = findSuccessor(root)Use helper to find successor

root.right = deleteNode(root.right, successor.val)Delete successor recursively

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

public class Solution {
    private TreeNode findSuccessor(TreeNode node) {
        TreeNode curr = node.right;
        while (curr.left != null) curr = curr.left;
        return curr;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = deleteNode(root.left, key);
        else if (key > root.val) root.right = deleteNode(root.right, key);
        else {
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode successor = findSuccessor(root);
                root.val = successor.val;
                root.right = deleteNode(root.right, successor.val);
            }
        }
        return root;
    }

    // main method omitted for brevity
}

Line Notes

private TreeNode findSuccessor(TreeNode node)Helper method to find inorder successor

TreeNode curr = node.right;Start from right child

while (curr.left != null)Go left as far as possible

if (key < root.val)Recurse left if key smaller

else if (key > root.val)Recurse right if key larger

if (root.left == null) return root.right;No left child, replace with right

else if (root.right == null) return root.left;No right child, replace with left

TreeNode successor = findSuccessor(root);Find successor using helper

root.right = deleteNode(root.right, successor.val);Delete successor recursively

#include <iostream>
using namespace std;

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

TreeNode* findSuccessor(TreeNode* node) {
    TreeNode* curr = node->right;
    while (curr->left) curr = curr->left;
    return curr;
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return NULL;
    if (key < root->val) root->left = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (!root->left) return root->right;
        else if (!root->right) return root->left;
        else {
            TreeNode* successor = findSuccessor(root);
            root->val = successor->val;
            root->right = deleteNode(root->right, successor->val);
        }
    }
    return root;
}

int main() {
    // Build BST and call deleteNode
    return 0;
}

Line Notes

TreeNode* findSuccessor(TreeNode* node)Helper function to find inorder successor

TreeNode* curr = node->right;Start from right child

while (curr->left) curr = curr->left;Go left as far as possible

if (key < root->val) root->left = deleteNode(root->left, key);Recurse left if key smaller

else if (key > root->val) root->right = deleteNode(root->right, key);Recurse right if key larger

if (!root->left) return root->right;No left child, replace with right

else if (!root->right) return root->left;No right child, replace with left

TreeNode* successor = findSuccessor(root);Find successor using helper

root->right = deleteNode(root->right, successor->val);Delete successor recursively

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

function findSuccessor(node) {
    let curr = node.right;
    while (curr.left) curr = curr.left;
    return curr;
}

function deleteNode(root, key) {
    if (!root) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else {
        if (!root.left) return root.right;
        else if (!root.right) return root.left;
        else {
            let successor = findSuccessor(root);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }
    }
    return root;
}

// Example usage:
// let root = new TreeNode(...);
// console.log(deleteNode(root, key));

Line Notes

function findSuccessor(node)Helper function to find inorder successor

let curr = node.right;Start from right child

while (curr.left) curr = curr.left;Go left as far as possible

if (key < root.val) root.left = deleteNode(root.left, key);Recurse left if key smaller

else if (key > root.val) root.right = deleteNode(root.right, key);Recurse right if key larger

if (!root.left) return root.right;No left child, replace with right

else if (!root.right) return root.left;No right child, replace with left

let successor = findSuccessor(root);Find successor using helper

root.right = deleteNode(root.right, successor.val);Delete successor recursively

⏱

Complexity

TimeO(h) where h is the height of the BST

SpaceO(h) due to recursion stack

Similar to approach 1, but code is cleaner due to helper function separation.

💡 This approach is easier to debug and maintain, especially in large codebases.

Interview Verdict: Accepted

This is a clean, maintainable recursive solution preferred in many interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The recursive approach with helper function is recommended for clarity and maintainability in 95% of interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive)	O(h)	O(h) recursion stack	Yes for very deep trees	N/A	Standard solution to implement and explain
2. Iterative with Parent Pointers	O(h)	O(1)	No	N/A	Good to mention or implement if recursion is a concern
3. Recursive with Helper Function	O(h)	O(h)	Yes	N/A	Preferred for clean, maintainable code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, and progressively improve your solution.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force recursive approach and its cases.Discuss iterative approach to avoid recursion stack.Explain helper function usage for cleaner code.Write code carefully handling all cases.Test with edge cases and explain time/space complexity.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of BST properties, handling of deletion cases, recursion or iteration skills, and code clarity.

Common Follow-ups

• How to handle duplicate keys? → BST usually has unique keys; duplicates require design decisions.
• Can you implement iterative deletion without parent pointers? → More complex, but possible with stack.

💡 These follow-ups test your depth of understanding and ability to handle variations or constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves BST node removal, 2) Must maintain BST property, 3) Need to handle three deletion cases, 4) Inorder successor/predecessor needed.

Signature Phrases

delete node in BSTinorder successornode with two children

NOT This Pattern When

Deleting nodes in a binary tree without BST property is a different pattern.

Similar Problems

Insert Node in BST - similar tree modificationFind Inorder Successor in BST - helper conceptValidate BST - understanding BST properties

Practice

1. You need to design an iterator over a binary search tree that returns elements in ascending order, but you want to avoid storing all elements upfront to save space. Which approach best fits this requirement?

easy

A. Use a divide-and-conquer approach to merge sorted lists from left and right subtrees at each next() call.

B. Perform a full inorder traversal upfront and store all elements in a list for O(1) next() calls.

C. Use a breadth-first traversal to visit nodes level by level and return elements in sorted order.

D. Use a controlled inorder traversal with a stack to lazily fetch the next smallest element on demand.

Solution

1. Step 1: Understand the problem constraints

   The iterator must return elements in ascending order without storing all nodes upfront to save space.

2. Step 2: Evaluate approaches

   Full inorder traversal (B) uses O(n) space upfront, breadth-first (C) does not guarantee sorted order, and divide-and-conquer merging (D) is inefficient per next() call. Controlled inorder traversal with a stack (A) lazily fetches the next smallest element using O(h) space, which is optimal for this problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Lazy stack-based inorder traversal matches the problem requirements [OK]

Hint: Lazy stack traversal avoids full storage [OK]

Common Mistakes:

• Thinking BFS returns sorted order
• Assuming full traversal is always best
• Confusing divide-and-conquer with lazy iteration

2. Consider the following code snippet implementing the optimal iterative approach to convert a BST to a Greater Tree. Given the BST with nodes [2, 1, 3], what is the value of the root node after the function completes?

easy

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Trace reverse inorder traversal order

   Nodes visited in order: 3, 2, 1.

2. Step 2: Accumulate sums and update nodes

   acc_sum=0 initially. - Visit 3: acc_sum=3, node.val=3 - Visit 2: acc_sum=3+2=5, node.val=5 - Visit 1: acc_sum=5+1=6, node.val=6 Root node was 2, updated to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Root node value after update is 5 [OK]

Hint: Reverse inorder sums nodes from largest to smallest [OK]

Common Mistakes:

• Confusing traversal order and updating nodes too early
• Off-by-one errors in accumulating sums
• Misidentifying which node is root after updates

3. Given the following code for finding the kth smallest element in a BST, what is the returned value when called with k=2 on the provided tree?

from typing import Optional

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

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right

# Tree:
#     3
#    / \
#   1   4
#    \
#     2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kthSmallest(root, 2))

easy

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Trace the inorder traversal steps

   Stack initially empty, current=root(3). Push 3, move left to 1. Push 1, move left to None. Pop 1 (count=1), move right to 2.

2. Step 2: Continue traversal to find kth=2

   Push 2, move left None. Pop 2 (count=2), return 2 as kth smallest.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Second smallest in BST is 2 [OK]

Hint: Inorder traversal visits nodes in ascending order [OK]

Common Mistakes:

• Off-by-one counting of k
• Returning before incrementing count

4. What is the worst-case time complexity of inserting a value into a binary search tree using the iterative insertion method shown below?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while 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

medium

A. O(1) because insertion is done at a leaf immediately

B. O(h) where h is the height of the tree, since traversal down the tree is needed

C. O(n) where n is the number of nodes, because all nodes might be visited

D. O(log n) always, because BSTs are balanced by definition

Solution

1. Step 1: Identify traversal cost

   Insertion requires traversing from root down to a leaf where the new node is inserted.

2. Step 2: Relate traversal to tree height

   In worst case, the tree is skewed, so height h can be up to n, but complexity is expressed as O(h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Traversal cost dominates insertion -> O(h) [OK]

Hint: Insertion cost depends on tree height, not always balanced [OK]

Common Mistakes:

• Assuming O(1) because insertion is at leaf
• Confusing height h with number of nodes n
• Assuming BST is always balanced

5. What is the time complexity of the optimal iterative algorithm for finding the lowest common ancestor in a BST, where h is the height of the tree and n is the number of nodes?

medium

A. O(log n), assuming the BST is balanced and height h = log n

B. O(n), because in the worst case the algorithm may visit all nodes

C. O(h), since the algorithm traverses from root down to the split point along one path

D. O(1), because the algorithm uses constant space and simple comparisons

Solution

1. Step 1: Identify traversal path length

   The algorithm moves from root down one path until the split point, visiting at most h nodes.

2. Step 2: Understand h vs n

   Height h can be up to n in worst case (skewed tree), but the question asks for optimal algorithm time complexity, which assumes balanced BST where h = log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal limited to one root-to-node path in balanced BST [OK]

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

Common Mistakes:

• Confusing worst-case O(n) with average-case O(log n)
• Assuming constant time due to simple comparisons
• Ignoring that recursion stack space is not used here