Is Delete Node in a BST easy or hard?

Delete Node in a BST is generally classified as a Medium difficulty problem. The challenge comes from correctly handling the three deletion scenarios and maintaining BST ordering while updating tree pointers.

Delete Node in a BST Python/Java solution

Python and Java implementations typically follow the same recursive strategy. Search for the key, handle the three deletion cases, and when two children exist replace the node value with the in-order successor from the right subtree before deleting that successor node.

How to solve Delete Node in a BST in O(n)?

A straightforward solution traverses the tree to locate the node and adjusts pointers during deletion. In the worst case where the BST becomes skewed like a linked list, the height becomes n, giving O(n) time complexity. Balanced BST structures typically reduce this to O(log n).

What is the best approach for Delete Node in a BST?

The best approach is in-place BST deletion using the in-order successor. Traverse the tree to find the node, then handle three cases: leaf node removal, single-child replacement, or replacing the node with its successor if it has two children. This keeps the BST ordering intact and runs in O(h) time where h is the tree height.

Is Delete Node in a BST asked at Google/Amazon/Meta?

Delete Node in a BST is a common tree interview problem and variations have appeared in interviews at companies like Google, Amazon, and Meta. Interviewers use it to test understanding of BST invariants, recursion, and handling multiple structural cases in tree manipulation.

What data structure is used in Delete Node in a BST?

The problem uses a Binary Search Tree data structure. BST properties allow efficient searching and deletion by ensuring that left subtree values are smaller and right subtree values are larger than the node value.

What is the time complexity of Delete Node in a BST?

Deletion in a Binary Search Tree takes O(h) time, where h is the height of the tree. In balanced BSTs this becomes O(log n), while in the worst case of a skewed tree it can degrade to O(n). Finding the node and locating the in-order successor both operate within the tree height.

Description Solution Video 12:59

450. Delete Node in a BST

Medium55.1% acceptance11 companies

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 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: 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 above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
Each node has a unique value.
root is a valid binary search tree.
-10⁵ <= key <= 10⁵

Follow up: Could you solve it with time complexity O(height of tree)?

Asked at 11 companies

Uber Oracle Flipkart Bytedance Amazon Bloomberg

Infosys LinkedIn

Google Microsoft Meta

Topics

12:59

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

450. Delete Node in a BST

Asked at 11 companies

Topics

Similar problems