Delete Nodes And Return Forest

Delete Nodes And Return Forest is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in todelete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], todelete = [3,5] Output: [[1,2,null,4],[6],[7]]

Example 2:

Input: root = [1,2,4,null,3], todelete = [3] Output: [[1,2,4]]

Constraints:

- The number of nodes in the given tree is at most 1000.

- Each node has a distinct value between 1 and 1000.

- todelete.length <= 1000

- todelete contains distinct values between 1 and 1000.

Topics and companies

Topics: Array, Hash Table, Tree, Depth-First Search, Binary Tree.

Reported in interviews at Google, Amazon, Facebook, Salesforce.

How to practise Delete Nodes And Return Forest on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of nodes in the tree. Each node is visited exactly once. time and O(N), for the recursion stack in the worst case (skewed tree) and for the result vector and to_delete_set. space.

Open Delete Nodes And Return Forest in the code editor, or read the Delete Nodes And Return Forest editorial for a worked solution with its approach and complexity analysis.

Where Delete Nodes And Return Forest sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Postorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Delete Nodes And Return Forest

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• All Nodes Distance K in Binary Tree — Medium, same subpattern
• Balanced Binary Tree — Easy, same subpattern
• Binary Tree Maximum Path Sum — Hard, same subpattern
• Binary Tree Postorder Traversal — Easy, same subpattern
• Diameter of Binary Tree — Easy, same subpattern
• Find Leaves of Binary Tree — Medium, same subpattern