Title: Delete Node in a Binary Search Tree

Description:

Given a binary search tree and a value key, delete the node corresponding to key in the binary search tree, and restore it using its right child, as shown in the diagram below, while maintaining the properties of the binary search tree. Return the level order traversal of the binary search tree (including all nodes of the complete binary tree representation of this tree, with missing nodes represented by null).

Generally, deleting a node can be divided into two steps:

First, find the node to be deleted.
If found, delete it.
Input:

The level order traversal of the binary search tree (including all nodes of the complete binary tree representation of this tree, with missing nodes represented by null) and the node to be deleted.

Output:

The level order traversal of the binary search tree after deletion (including all nodes of the complete binary tree representation of this tree, with missing nodes represented by null).

Sample Input 1:

5,3,6,2,4,null,7
3
Sample Output 1:

5,4,6,2,null,null,7
Sample Input 2:

5,3,6,2,4,null,7
0
Sample Output 2:

5,3,6,2,4,null,7

Question

Title: Delete Node in a Binary Search Tree

Description:

Given a binary search tree and a value key, delete the node corresponding to key in the binary search tree, and restore it using its right child, as shown in the diagram below, while maintaining the properties of the binary search tree. Return the level order traversal of the binary search tree (including all nodes of the complete binary tree representation of this tree, with missing nodes represented by null).

Generally, deleting a node can be divided into two steps:

First, find the node to be deleted.
If found, delete it.
Input:

The level order traversal of the binary search tree (including all nodes of the complete binary tree representation of this tree, with missing nodes represented by null) and the node to be deleted.

Output:

The level order traversal of the binary search tree after deletion (including all nodes of the complete binary tree representation of this tree, with missing nodes represented by null).

Sample Input 1:

5,3,6,2,4,null,7
3
Sample Output 1:

5,4,6,2,null,null,7
Sample Input 2:

5,3,6,2,4,null,7
0
Sample Output 2:

5,3,6,2,4,null,7

Accepted Answer

```python # Define a class for the TreeNode class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val # Node value self.left = left # Left child self.right = right # Right child # Function to delete a node in a BST def deleteNode(root, key): if not root: return root # If root is None, return None # If the key to be deleted is smaller than the root's key, then it lies in left subtree if key < root.val: root.left = deleteNode(root.left, key) # If the key to be deleted is greater than the root's key, then it lies in right subtree elif key > root.val: root.right = deleteNode(root.right, key) # If key is same as root's key, then this is the node to be deleted else: # Node with only one child or no child if not root.left: return root.right elif not root.right: return root.left # Node with two children: Get the inorder successor (smallest in the right subtree) temp = minValueNode(root.right) root.val = temp.val # Copy the inorder successor's content to this node root.right = deleteNode(root.right, temp.val) # Delete the inorder successor return root # Function to find the node with the minimum value def minValueNode(node): current = node while current.left: current = current.left return current # Function to perform level order traversal def levelOrderTraversal(root): if not root: return [] result, queue = [], [root] while queue: node = queue.pop(0) if node: result.append(node.val) queue.append(node.left) queue.append(node.right) else: result.append(None) return result ``` ```python # Main function that tests deleteNode and levelOrderTraversal def main(): # Test case 1 root1 = TreeNode(5) root1.left = TreeNode(3) root1.right = TreeNode(6) root1.left.left = TreeNode(2) root1.left.right = TreeNode(4) root1.right.right = TreeNode(7) key1 = 3 root1 = deleteNode(root1, key1) assert levelOrderTraversal(root1) == [5, 4, 6, 2, None, None, 7] # Test case 2 root2 = TreeNode(5) root2.left = TreeNode(3) root2.right = TreeNode(6) root2.left.left = TreeNode(2) root2.left.right = TreeNode(4) root2.right.right = TreeNode(7) key2 = 0 root2 = deleteNode(root2, key2) assert levelOrderTraversal(root2) == [5, 3, 6, 2, 4, None, 7] # Run the main function main() ``` ∻Explanation∻ ⚹The code defines a TreeNode class, a function to delete a node in a BST, a helper function to find the minimum value node, and a function to perform level order traversal. The main function tests these functions with two test cases.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Define the TreeNode class to represent each node in the binary search tree. ‖ ‖ ▪ ⋮ Implement the deleteNode function to handle the deletion of a node in the BST. ‖ ‖ ▪ ⋮ Implement the minValueNode function to find the smallest node in the right subtree. ‖ ‖ ▪ ⋮ Implement the levelOrderTraversal function to return the level order traversal of the BST. ‖ ‖ ▪ ⋮ Define the main function to test the deleteNode and levelOrderTraversal functions with two test cases. ‖ ∻Time Complexity∻ ⚹The time complexity for deleting a node in a BST is O(h), where h is the height of the tree.⚹ ∻Space Complexity∻ ⚹The space complexity is O(h) due to the recursion stack.⚹

Sia