Delete Nodes And Return Forest Solution for Google

Company: Google · Difficulty: Hard · Topics: Tree, Depth-First Search

Problem Statement

Given the root of a binary tree, each node has a value, and an integer target.

Return a forest (an array of trees) after deleting all nodes with a value equal to target.

A forest is a collection of disjoint trees. You may return the result in any order.

Examples

Example 1:

Input: root = [1,2,3,4,5,6,7], target = 3

Output: [[1,2,4,5],[6,7]]

Explanation:

The first figure represents the initial tree.

After deleting node 3, the tree becomes two trees with disjoint nodes.

Example 2:

Input: root = [1,2,3,4,5,6,7], target = 7

Output: [[1,2,3,4,5,6]]

Explanation:

After deleting node 7, the tree becomes one tree with all nodes.

Intuition

The problem can be approached using a Depth-First Search (DFS) to traverse the tree and identify nodes to delete. We need to handle the case where the root itself is the target value.

Approach

1. Traverse the tree using DFS.

2. If the current node's value is equal to the target, we need to delete it.

3. If the current node is a leaf node, we can delete it directly.

4. If the current node has children, we need to decide which child to keep.

5. If the current node is not the target, we add it to the result forest.

6. If the current node is the target and is the root, we need to handle the case where the root itself is the target.

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution: DFS with Post-Order Traversal

Time Complexity: O(n) - Where n is the number of nodes in the tree

Space Complexity: O(h) - Where h is the height of the tree, for recursion stack