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. What is the time complexity of balancing a BST using the optimal approach of inorder traversal followed by iterative balanced BST construction from the collected nodes?

medium

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

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

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

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

Solution

1. Step 1: Analyze inorder traversal time

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

2. Step 2: Analyze balanced BST construction time

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

3. Step 3: Consider sorting complexity

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

4. Final Answer:

   Option A -> Option A

5. Quick Check:

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

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

Common Mistakes:

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

3. The following code attempts to find the lowest common ancestor in a BST. Identify the bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

medium

A. Line 3: Using '<=' and '>=' instead of '<' and '>' causes incorrect ancestor detection.

B. Line 6: Returning current too early without checking if current matches p or q.

C. Line 4: Not handling null root before loop causes crash on empty tree.

D. Line 5: Moving current to left or right without verifying if child exists causes errors.

Solution

1. Step 1: Analyze comparison operators

   Using '<=' and '>=' causes the loop to move past the node when p or q equals current, missing the case where current is ancestor of itself.

2. Step 2: Correct operator usage

   Changing to '<' and '>' ensures the loop stops at the correct ancestor node, including when one node is ancestor of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive comparisons skip valid ancestor nodes [OK]

Hint: Use strict inequalities to detect ancestor nodes correctly [OK]

Common Mistakes:

• Assuming ancestor must be strictly above nodes
• Ignoring null root edge cases
• Returning too early without validation

4. The following code attempts to validate a BST using inorder traversal. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line checking if node is null (if not node: return true)

B. Line updating prev[0] = node.val

C. Line comparing node.val < prev[0] instead of node.val <= prev[0]

D. Line calling inorder(node.left)

Solution

1. Step 1: Identify BST strict inequality

   BST requires node.val to be strictly greater than previous inorder value; using < instead of <= allows duplicates.

2. Step 2: Understand impact of bug

   Using node.val < prev[0] misses the case when node.val == prev[0], incorrectly allowing duplicates and invalid BSTs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Strict inequality check is essential to reject duplicates [OK]

Hint: BST nodes must be strictly increasing in inorder traversal [OK]

Common Mistakes:

• Allowing duplicates by using < instead of <=
• Not resetting prev between calls
• Only comparing immediate children

5. Suppose the BST validation problem is modified so that duplicate values are allowed only on the right subtree (i.e., node values in the right subtree can be equal to the current node). Which modification to the inorder traversal check correctly validates this variant?

hard

A. Change the comparison to node.val < prev[0] to allow duplicates on the right subtree.

B. Change the comparison to node.val < prev[0] for all nodes except when node is right child, then allow node.val == prev[0].

C. Change the comparison to node.val <= prev[0] to allow duplicates anywhere.

D. Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree.

Solution

1. Step 1: Understand variant allowing duplicates only on right subtree

   Duplicates allowed only if they appear in right subtree, so inorder sequence can have equal values only when moving right.

2. Step 2: Modify comparison accordingly

   During inorder traversal, allow node.val == prev[0] only if current node is right child of previous node; otherwise, enforce strict inequality.

3. Step 3: Reason why other options fail

   Change the comparison to node.val < prev[0] to allow duplicates on the right subtree. allows duplicates anywhere; Change the comparison to node.val <= prev[0] to allow duplicates anywhere. allows duplicates anywhere; Change the comparison to node.val < prev[0] only when traversing left subtree, and node.val <= prev[0] when traversing right subtree. is ambiguous and not implementable in simple inorder traversal without parent info.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Allow duplicates only on right subtree requires conditional equality check [OK]

Hint: Duplicates allowed only on right subtree require conditional comparison [OK]

Common Mistakes:

• Allowing duplicates anywhere
• Ignoring subtree direction in comparison
• Using simple <= everywhere