Coding - Tree Levels After Node Deletions II

Here is the full interview question "Coding - Tree Levels After Node Deletions II" asked at xAI:

Problem Statement

Given the root of a binary tree, each node of the tree has a distinct value and it's given that the tree is a Binary Search Tree (BST). After deleting all nodes with a value in to_delete, return the tree levels of the resulting tree in a list, where each level is sorted in ascending order.

A node is considered deleted if it is in to_delete or if all of its descendants are in to_delete. You need to return the result in any order.

Examples

1. Example 1:

   plaintext Input: root = [1,2,3,4,5,6,7], to_delete = [3,6] Output: [[1,2,4,5,7]] Explanation: After deleting nodes with value in [3,6], the resulting tree is: 1 / \ 2 4 / \ 5 7 The tree levels are [1,2,4,5,7].

2. Example 2:

   plaintext Input: root = [1,2,3,4,5,6,7,8,9,10], to_delete = [1,3,4,5,6,7,8,10] Output: [[2,9]] Explanation: After deleting nodes with value in [1,3,4,5,6,7,8,10], the resulting tree is: 2 \ 9 The tree levels are [2,9].

Constraints

• The number of nodes in the tree is in the range [1, 10^5].
• The value of each node is between [1, 10^5].
• to_delete.length is in the range [0, 10^5].
• to_delete does not contain duplicates.

Hints

1. Use a BST property to optimize the deletion process.
2. Perform a level order traversal to collect the levels after deletion.

Solution

`python class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

class Solution: def deleteNode(self, root: TreeNode, key: int) -> TreeNode: if not root: return None if root.val > key: root.left = self.deleteNode(root.left, key) elif root.val < key: root.right = self.deleteNode(root.right, key) else: return root.right if not root.left else self.getLowest(root.left) return root

def getLowest(self, node: TreeNode) -> TreeNode:
    while node.left:
        node = node.left
    return node

def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[List[int]]:
    deleted = set(to_delete)
    root = self.deleteNode(root, *deleted)
    
    def levelOrder(node):
        if not node:
            return []
        result, queue = [], [node]
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node:
                    level.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
            result.append(sorted([x for x in level if x not in deleted]))
        return result
    
    return levelOrder(root)

`

Source: LeetCode (https://leetcode.com/problems/tree-levels-after-node-deletions-ii/)