Step 4 of 4
Three-Case Node Deletion
You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.
Node deletion is the most subtle BST operation because removing a node must preserve the binary search invariant for all subtrees.
Implement delete(val) handling all 3 cases:
- Case 1: Leaf Node (0 children) $\to$ Remove node reference by returning
null. - Case 2: 1 Child $\to$ Replace node with its single non-null child.
- Case 3: 2 Children $\to$ Find the in-order successor (the minimum node in the right subtree), copy its value into the current node, and recursively delete the successor from the right subtree.
Return true if the node was deleted, or false if it was not found.
Your build
Running is free — Submit is what records the step. Or press ⌘↩
Tests
1 case| call | type | expected | result |
|---|---|---|---|
| runOps([["insert",50],["insert",30],["insert",70],["insert",20],["insert",40],["insert",60],["insert",80],["delete",20],["inOrder"],["delete",30],["inOrder"],["delete",50],["inOrder"],["delete",999],["size"]]) | deletes leaf, single-child, and two-child nodes | [null,null,null,null,null,null,null,true,[30,40,50,60,70,80],true,[40,50,60,70,80],true,[40,60,70,80],false,4] | — |
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left