31 days Challenge — Challenge completed!

Delete Node in a BST Problem

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3
5
   / \
  3   6
 / \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
   / \
  4   6
 /     \
2       7
Another valid answer is [5,2,6,null,4,null,7].
5
   / \
  2   6
   \   \
    4   7

Solution

Here you can see the performance of my solution (keep in mind that Runtime can vary depending on the server):

My statistic for the memory does not appear because it is in the right, so it has been bad.

So, now that the challenge is finished I got the habit of doing the exercises, and it is helping me to keep problem solving skills, because sometimes at work we could be busy with different meetings that make us stop coding and keeping this problem solving skills. So, I will try to continue doing the exercises or at least, I will continue taking a look to the problems and thinking on a solution.

Thanks a lot to all of you that encouraged me to continue the challenge and finishing it.

You can follow me on LinkedIn.