How do you solve Delete Node in a BST on LeetCode?

Delete Node in a BST (LeetCode #450) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Understanding the properties of BSTs is crucial for efficient deletion.

What is the brute force solution for Delete Node in a BST?

The brute force approach for Delete Node in a BST is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves searching for the node to delete and then manually reconstructing the tree without that node. This is straightforward but inefficient, especially for large trees. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Delete Node in a BST?

Delete Node in a BST uses the following concepts: Tree, Binary Search Tree, Binary Tree. The recommended patterns to study are: Tree Traversal, Recursion.

What are the interview tips for Delete Node in a BST?

Explain your thought process clearly while coding. Consider edge cases such as deleting from an empty tree. Practice writing out the tree structure and how it changes during deletion.

What are common mistakes when solving Delete Node in a BST?

Not considering all cases when deleting a node. Failing to maintain the BST properties after deletion.

#450

Delete Node in a BST

Medium

TreeBinary Search TreeBinary TreeTree TraversalRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

The optimal approach leverages the properties of a Binary Search Tree (BST) to efficiently find and delete the node while maintaining the tree structure. This method ensures that we only traverse the tree as necessary.

⚙️

Algorithm

3 steps

1Step 1: Start at the root and search for the node with the given key.
2Step 2: If the node is found, handle three cases: no children, one child, or two children.
3Step 3: For two children, find the in-order successor, replace the node's value, and delete the successor.

solution.py25 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def deleteNode(root, key):
9    if not root:
10        return root
11    if key < root.val:
12        root.left = deleteNode(root.left, key)
13    elif key > root.val:
14        root.right = deleteNode(root.right, key)
15    else:
16        if not root.left:
17            return root.right
18        elif not root.right:
19            return root.left
20        temp = root.right
21        while temp.left:
22            temp = temp.left
23        root.val = temp.val
24        root.right = deleteNode(root.right, temp.val)
25    return root

ℹ

Complexity note: The time complexity is O(n) in the worst case (unbalanced tree), but O(h) in balanced trees, where h is the height of the tree. Space complexity is O(h) due to the recursive call stack.

1Understanding the properties of BSTs is crucial for efficient deletion.
2Handling all three cases (no children, one child, two children) is essential for correct implementation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.