Vultr DocsLatest Content

Delete Nodes And Return Forest

Updated on 22 May, 2025
Delete Nodes And Return Forest header image

Problem Statement

Given a binary tree where each node is uniquely identified by a distinct value, we are tasked with removing specific nodes as dictated by a list to_delete. The removal of these nodes fragments the original tree into multiple smaller trees, collectively referred to as a forest. Our goal is to identify and return a list of the root nodes for each component tree that remains post-deletion. This outcome should encompass all trees in the resultant forest, and the order of presentation for these root nodes is flexible.

Examples

Example 1

Input:

root = [1,2,3,4,5,6,7], to_delete = [3,5]

Output:

[[1,2,null,4],[6],[7]]

Example 2

Input:

root = [1,2,4,null,3], to_delete = [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.
  • to_delete.length <= 1000
  • to_delete contains distinct values between 1 and 1000.

Approach and Intuition

  1. The task requires traversing the entire tree once to potentially delete the required nodes and also to keep track of the new roots formed if the subtrees get disconnected from the original tree.

  2. A straightforward intuition here is to perform a depth-first search (DFS) on the tree. During the traversal:

    • If we encounter a node that needs deletion, we perform the required operations to sever this node from the tree.
    • For its child nodes, if they are not to be deleted, these become new roots of the subtrees formed due to the deletion.

  3. Before initiating the DFS, it's beneficial to convert the to_delete array into a set for O(1) complexity checks during node deletions.

  4. During DFS:

    • Check if the current node needs to be deleted.
    • Recursively apply DFS to the children (left and right).
    • If deleting a node, ensure that if the node has any children, they are recorded as new potential roots.

  5. Handling the roots of the subtrees:

    • If the node to be deleted is the root and it has children, those children (if not in to_delete) become new roots.
    • If a node has parent and isn't marked for deletion nor are its children, simply continue the traversal.

  6. The recursive nature of DFS simplifies checking and updating the parent-child relationship as we only need to look at the immediate nodes (parent and children) for any adjustments in links due to deletions.

By following this approach, we maximize the efficiency of forming the resultant forest by ensuring each node is visited once, and decisions are made on-the-go about node deletion and subtree root formation. This method also conveniently handles edge cases like deleting leaf nodes or the entire tree.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    vector<TreeNode*> removeNodes(TreeNode* root, vector<int>& deletions) {
        if (!root) return {};

        unordered_set<int> deleteNodes(deletions.begin(), deletions.end());
        vector<TreeNode*> resultingForest;

        queue<TreeNode*> processQueue;
        processQueue.push(root);

        while (!processQueue.empty()) {
            TreeNode* activeNode = processQueue.front();
            processQueue.pop();

            if (activeNode->left) {
                processQueue.push(activeNode->left);
                if (deleteNodes.count(activeNode->left->val)) {
                    activeNode->left = nullptr;
                }
            }

            if (activeNode->right) {
                processQueue.push(activeNode->right);
                if (deleteNodes.count(activeNode->right->val)) {
                    activeNode->right = nullptr;
                }
            }

            if (deleteNodes.count(activeNode->val) != 0) {
                if (activeNode->left) {
                    resultingForest.push_back(activeNode->left);
                }
                if (activeNode->right) {
                    resultingForest.push_back(activeNode->right);
                }
            }
        }

        if (deleteNodes.count(root->val) == 0) {
            resultingForest.push_back(root);
        }

        return resultingForest;
    }
};

The solution involves using a C++ class that defines a method to remove specific nodes from a binary tree and returns the resulting forest. The method removeNodes takes two parameters: a pointer to the root node of the binary tree (TreeNode* root) and a vector of integers (vector<int>& deletions) that lists the values of nodes to be deleted.

  • Initiate by converting the deletions vector into an unordered set deleteNodes for fast lookup.
  • Use a vector<TreeNode*> named resultingForest to store the roots of the trees in the new forest.
  • Traverse the tree using a queue processQueue to handle nodes level by level.
  • For each node being processed:
    • If its left child exists and should be deleted, detach it by setting activeNode->left to nullptr.
    • If its right child exists and should be deleted, detach it by setting activeNode->right to nullptr.
    • If the current node is deleted, consider its detached children (if they exist) as new roots and add them to resultingForest.
  • After processing all nodes, if the root was not among the deletions, add it to resultingForest.

Finally, resultingForest is returned, which contains the roots of all trees resulting from the deletions. This solution effectively creates a new set of binary trees where specified nodes have been removed.

java 
class Solution {

    public List<TreeNode> removeNodes(TreeNode rootNode, int[] toRemove) {
        if (rootNode == null) {
            return new ArrayList<>();
        }

        Set<Integer> deleteSet = new HashSet<>();
        for (int id : toRemove) {
            deleteSet.add(id);
        }

        List<TreeNode> remainingForest = new ArrayList<>();

        Queue<TreeNode> queueOfNodes = new LinkedList<>();
        queueOfNodes.add(rootNode);

        while (!queueOfNodes.isEmpty()) {
            TreeNode current = queueOfNodes.poll();

            if (current.left != null) {
                queueOfNodes.add(current.left);
                if (deleteSet.contains(current.left.val)) {
                    current.left = null;
                }
            }

            if (current.right != null) {
                queueOfNodes.add(current.right);
                if (deleteSet.contains(current.right.val)) {
                    current.right = null;
                }
            }

            if (deleteSet.contains(current.val)) {
                if (current.left != null) {
                    remainingForest.add(current.left);
                }
                if (current.right != null) {
                    remainingForest.add(current.right);
                }
            }
        }

        if (!deleteSet.contains(rootNode.val)) {
            remainingForest.add(rootNode);
        }

        return remainingForest;
    }
}

The Java solution provided handles the problem of deleting specified nodes from a given tree and returning a list of remaining trees. Aim to understand how the method, removeNodes, executes this task using a breadth-first search approach:

  1. Initializes a HashSet named deleteSet to store the values that need removal. It populates this set using the array toRemove.
  2. Creates an ArrayList named remainingForest to store the trees that remain after deletion.
  3. Utilizes a Queue to hold nodes for level order traversal (breadth-first search), starting with the rootNode.
  4. Within a loop, processes each node in the queue:
    • First, checks if the current node's left or right child exists and adds them to the queue.
    • Then, evaluates whether these children are in the deleteSet. If so, detach them (i.e., set them to null to "delete" that subtree).
    • If the current node itself is in the deleteSet, adds its non-null children to remainingForest because they become new roots post-deletion.
  5. At the end of traversal, if the root node itself isn't marked for deletion, adds it to remainingForest.
  6. Finally, returns remainingForest containing all the roots of the remaining trees after the nodes deletion.

This method efficiently separates the tree into multiple subtrees by removing specified nodes and ensures the remaining nodes are intact as new separate trees. Each part of the tree either becomes a new forest or gets disconnected based on the deleteSet.

python 
class Solution:
    def deleteNodes(
        self, root: Optional[TreeNode], to_eliminate: List[int]
    ) -> List[TreeNode]:
        if not root:
            return []

        delete_set = set(to_eliminate)
        remaining_trees = []

        queue = deque([root])

        while queue:
            node = queue.popleft()

            if node.left:
                queue.append(node.left)
                if node.left.val in delete_set:
                    node.left = None

            if node.right:
                queue.append(node.right)
                if node.right.val in delete_set:
                    node.right = None

            if node.val in delete_set:
                if node.left:
                    remaining_trees.append(node.left)
                if node.right:
                    remaining_trees.append(node.right)

        if root.val not in delete_set:
            remaining_trees.append(root)

        return remaining_trees

This Python solution addresses the problem of deleting specified nodes from a binary tree and returning the remaining parts of the tree as a list of separate trees (forest). The given code performs this operation using breadth-first traversal:

  • A set (delete_set) is created to quickly check if a node needs to be deleted, improving efficiency.
  • The algorithm uses a queue to execute the breadth-first traversal, starting with pushing the root node into the queue.
  • Within the traversal loop, the code checks each node's left and right child. If either child is in the delete_set, it is removed by setting it to None.
  • If the current node itself is in the delete_set, the function checks and adds its children to the remaining_trees list if they exist and are not marked for deletion.
  • Finally, if the root node of the tree is not marked for deletion, it's added to the remaining_trees list.

This function makes sure that after nodes deletion:

  • Any disconnected sub-trees become individual trees themselves.
  • Only non-deleted nodes and their sub-trees are returned.
  • The method efficiently deals with the deletion and segregation of the tree's nodes using set for fast access and a queue for systematic tree traversal.

Comments

No comments yet.