Delete node in BST
Filed under Walmart · Also reported at Vehant Technologies
Free read 2 of 3Traverse the tree to find the target node.
The question
Describe the algorithm to delete a node from a Binary Search Tree (BST) while maintaining the BST property.
Constraints
- Node may have 0, 1, or 2 children
- Must maintain O(h) height complexity
Examples
- Input
- Delete 20 from tree [10, 20, 30]
- Output
- Tree [10, 30]
- Why
- 20 is a leaf, simply remove it.
Approach
Traverse the tree to find the target node.
Case 1: Leaf node (delete). Case 2: One child (replace with child). Case 3: Two children (find in-order successor, swap values, delete successor).
Time complexity is O(h) where h is tree height. Space is O(h) for recursion stack.
Tips
- What they are testing: Tests understanding of tree traversal and pointer manipulation.
- Common mistake: Forgetting to handle the case where the node to be deleted has two children (requires finding the in-order successor).
Follow-ups
- Discuss time complexities
Related Walmart questions
Collected from public candidate posts and coding forums. Updated Nov 2026.