# Leetcode 450 - Delete node in BST

Note

• It’s easy to find the pattern but hard to cover all the cases.
• Replace target with its right subtree and then append its left subtree to its right subtree. (Easy, right?)
• Need to learn how to write efficent recursion when we have to return a node. Code like root.left = recursion(root) is useful!
• Need to know just by assign a new node to an old node won’t change anything. You have to specify their relations by node1.left = node2.

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:

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

Example

My solution (Not optimal)

Optimal Recursion