< Back





450. Delete Node in a BST

This problem is actually pretty tough. If you don't know about how predecessors and successors work
in a binary search tree, this problem is going to be pretty hard to solve. You can find the
predecessor for a particular node by going left once and then going right until you can't go right
anymore - vice versa for the successor.

Knowing this, we search the binary tree until we find our target node for deletion. If the node is a
leaf, we can just set it to None. If the right child exists for a node, we find the successor and
replace our current value with the successor's value. Then we recursively travel the right subtree
to delete the successor.

If the right node doesn't exist, but the left does, we find the predecessor and do the same -
setting our value to the predecessor and recursively deleting the predecessor from the left subtree.

The solution is as follows:


  class Solution:
      def successor(self, root: TreeNode) -> int:
          root = root.right
          while root.left:
              root = root.left
          return root.val

      def predecessor(self, root: TreeNode) -> int:
          root = root.left
          while root.right:
              root = root.right
          return root.val

      def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
          if not root:
              return

          if key > root.val:
              root.right = self.deleteNode(root.right, key)
          elif key < root.val:
              root.left = self.deleteNode(root.left, key)
          else:
              if not root.left and not root.right:
                  root = None
              elif root.right:
                  root.val = self.successor(root)
                  root.right = self.deleteNode(root.right, root.val)
              else:
                  root.val = self.predecessor(root)
                  root.left = self.deleteNode(root.left, root.val)

          return root


_ Time Complexity:

  O(h) - Where h is the height of the tree.

_ Space Complexity:

  O(h) - Our recursive function can be called h times.