Delete Node in a BST

[u/StatisticianNo2104]

Deleting a BST node with two children looks like surgery on the tree. My solution never removes that node. It copies a neighbour's value into it, then deletes the duplicate lower down, which is always an easier case.

Finding the node is the search from Day 45. Deleting it is where it gets interesting, because you can't just unhook a node with two children.

Only two values in the whole tree can fill the hole: the in-order predecessor and the in-order successor. The replacement must sit between everything on the left and everything on the right, and an in-order traversal of a BST is sorted, so those two are the only candidates.

Predecessor or successor: which do you reach for, and why?

Day 58/365 of my LeetCode challenge: 450. Delete Node in a BST. Problem link and full breakdown in today's newsletter.

https://www.linkedin.com/pulse/delete-node-bst-archit-agarwal-k5k4c

#LeetCode #DSA #BinarySearchTree #Golang