Jobs

Interviews

Discussions

Delete Nodes And Return Forest

Medium

Asked by:

More companies

67 views

Topics:

TreesRecursion

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

After deleting all nodes with a value in to_delete, 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], 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.

Try coding it in LeetCode

Delete Nodes And Return Forest

Medium

Asked by:

67 views

Topics:

TreesRecursion

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

After deleting all nodes with a value in to_delete, 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], 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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `node.val` in the tree?
Can the `to_delete` array contain duplicate values?
Can the `to_delete` array be empty, or can it contain values that are not present in the tree?
In the resulting forest, is there a specific ordering required for the trees?
If a node is deleted and has both left and right children, should both children be added to the forest (assuming they aren't in `to_delete`)?

Brute Force Solution

Approach

The brute force approach to deleting nodes and returning a forest involves checking every single node to see if it should be removed. For each possible removal, we reconstruct the forest and see what we're left with.

Here's how the algorithm would work step-by-step:

First, look at each node in the tree individually.
For each node, imagine deleting it from the tree.
When you delete a node, you might create separate, smaller trees (a forest).
Record the roots of these new smaller trees.
After considering deleting each node individually, then try deleting every possible combination of two nodes.
Repeat this process for all possible combinations of nodes: three nodes, four nodes, and so on, up to deleting all the nodes.
For each combination of deleted nodes, identify the roots of the remaining trees.
From all these possible forests that you have generated, return the one that corresponds to exactly deleting the nodes specified in the 'to delete' list.

Code Implementation

def delete_nodes_and_return_forest_brute_force(root, to_delete):
    all_possible_forests = []

    def get_forest_roots(node, current_deleted_nodes):
        if node is None:
            return []

        forest_roots = []
        
        if node.val not in current_deleted_nodes:
            is_root = True
            
            #Check if the node is a root by iterating through every node in the tree
            #to see if current node is a child of a deleted node.
            def check_if_child(potential_parent, node_val):
                if potential_parent is None:
                    return False
                if potential_parent.left and potential_parent.left.val == node_val:
                    return True
                if potential_parent.right and potential_parent.right.val == node_val:
                    return True
                return check_if_child(potential_parent.left, node_val) or check_if_child(potential_parent.right, node_val)

            #If any of the nodes in the tree has current node as a child node then it's not a root
            def is_actually_a_root(root_node):
                #Iterate through every node in the tree
                def helper(node):
                    if node is None:
                        return False
                    if node.val in current_deleted_nodes and check_if_child(node, root_node.val):
                        return True
                    return helper(node.left) or helper(node.right)
                
                # Call helper from the tree root
                return not helper(root)

            if is_actually_a_root(node):
                forest_roots.append(node)

        forest_roots.extend(get_forest_roots(node.left, current_deleted_nodes))
        forest_roots.extend(get_forest_roots(node.right, current_deleted_nodes))

        return forest_roots

    # Generate all possible combinations of nodes to delete
    number_of_nodes = 0
    def count_nodes(node):
        nonlocal number_of_nodes
        if not node: return
        number_of_nodes += 1
        count_nodes(node.left)
        count_nodes(node.right)
    count_nodes(root)

    for i in range(1 << number_of_nodes):
        current_deleted_nodes = []
        all_nodes_list = []
        
        # Extract all nodes from the tree into a list to iterate
        def get_all_nodes(node):
            if node is None:
                return
            all_nodes_list.append(node.val)
            get_all_nodes(node.left)
            get_all_nodes(node.right)
        get_all_nodes(root)

        # Find the nodes that are going to be deleted in current iteration
        for j in range(number_of_nodes):
            if (i >> j) & 1:
                current_deleted_nodes.append(all_nodes_list[j])

        # Now we extract the forest by passing the current nodes to delete
        forest = get_forest_roots(root, current_deleted_nodes)
        all_possible_forests.append((current_deleted_nodes, forest))

    # Find the forest that corresponds to exactly deleting the nodes in 'to_delete'
    for deleted_nodes, forest in all_possible_forests:
        if sorted(deleted_nodes) == sorted(to_delete):
            #The combination of nodes to delete matches to_delete, returning the forest
            return forest

    return []

Big(O) Analysis

Time Complexity

O(2^n * n) – The described brute-force approach considers all possible subsets of nodes to delete. There are 2^n possible subsets for a tree with n nodes. For each subset, we potentially need to traverse the entire tree of n nodes to identify the roots of the remaining forest. Therefore, the time complexity is approximately O(2^n * n), dominated by the enumeration of all subsets and tree traversal.

Space Complexity

O(2^N * N) – The brute force approach described generates all possible combinations of nodes to delete. There are 2^N possible combinations of nodes to delete from the tree, where N is the number of nodes in the tree. For each combination, the algorithm identifies the roots of the resulting forest, which could contain up to N nodes in the worst case (where each node is a separate tree). Therefore, the space complexity is O(2^N * N), accounting for storing all the possible combinations and their resulting roots.

Optimal Solution

Approach

The goal is to remove specified nodes from a tree, resulting in a forest of smaller trees. We'll traverse the tree, identifying nodes to be deleted and adjusting the tree structure accordingly. This ensures that after deletion, all the remaining connected components are returned as the resulting forest.

Here's how the algorithm would work step-by-step:

First, make a list of the values that we want to delete from the tree.
Think of the entire tree as a single forest at the beginning.
Go through each node in the tree, starting from the root.
When you find a node that needs to be deleted:
Remove it from its parent. If it had a parent, then the parent is now the root of a new tree in our forest.
Add the deleted node's children to the forest as separate trees, if they exist. Each child now becomes the root of a new tree.
Keep doing this for every node in the tree.
After you have processed all the nodes, return the list of root nodes in your forest. This will be all the roots from the original tree, plus any roots from the deleted node's children.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def delete_nodes_and_return_forest(root, to_delete):
    nodes_to_delete_set = set(to_delete)
    forest = []

    def helper(node, is_root):
        if not node:
            return None

        # Traverse subtrees first
        node_should_be_deleted = node.value in nodes_to_delete_set
        node.left = helper(node.left, node_should_be_deleted)
        node.right = helper(node.right, node_should_be_deleted)

        # If the current node needs to be deleted
        if node_should_be_deleted:
            # Add children to the forest
            if node.left:
                forest.append(node.left)
            if node.right:
                forest.append(node.right)
            return None

        # If the current node is a root and not deleted, add to forest
        if is_root:
            forest.append(node)
        return node

    helper(root, True)

    return forest

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the tree once, as it performs a tree traversal. Creating the deletion list from the input array takes O(d) time where d is the number of nodes to delete, and d <= n. The tree traversal itself (steps 3-7) involves constant-time operations at each node: checking if the node is in the deletion list and adjusting parent-child relationships. Therefore the time complexity is dominated by the tree traversal, resulting in O(n) where n is the number of nodes in the tree. Thus, O(n) + O(d) simplifies to O(n).

Space Complexity

O(N) – The space complexity is dominated by the recursion depth of the tree traversal. In the worst-case scenario, such as a skewed tree, the recursion stack can grow to a depth of N, where N is the number of nodes in the tree. Additionally, to store the resulting forest (the list of root nodes), we might need to store up to N nodes in the worst-case scenario where all nodes become roots after deletions. Therefore, the auxiliary space used is O(N) for the recursion stack plus O(N) for the forest which simplifies to O(N).

Edge Cases

Case	How to Handle
Null root	If the root is null, return an empty list because there's no tree to process.
Empty 'to_delete' list	If 'to_delete' is empty, return a list containing only the root node.
All nodes need to be deleted	If all nodes are in 'to_delete', return an empty list indicating no forest remains.
Large tree and large 'to_delete' list causing recursion depth issues	The solution should be iterative or use a tree traversal approach to avoid stack overflow errors.
Tree is skewed heavily to one side (left or right)	Ensure the algorithm doesn't exhibit worst-case time complexity in skewed tree scenarios; an iterative solution helps.
Duplicate values in 'to_delete' list	Treat the 'to_delete' list as a set to avoid unnecessary repeated lookups during node deletion.
Deleting the root node	Handle the root node deletion specifically, adding its children to the result if they are not also being deleted.
'to_delete' contains values not present in the tree	The algorithm should handle gracefully by simply ignoring these values in the to_delete array during the traversal process.

Null root

How to Handle:

If the root is null, return an empty list because there's no tree to process.

Empty 'to_delete' list

How to Handle:

If 'to_delete' is empty, return a list containing only the root node.

All nodes need to be deleted

How to Handle:

If all nodes are in 'to_delete', return an empty list indicating no forest remains.

Large tree and large 'to_delete' list causing recursion depth issues

How to Handle:

The solution should be iterative or use a tree traversal approach to avoid stack overflow errors.

Tree is skewed heavily to one side (left or right)

How to Handle:

Ensure the algorithm doesn't exhibit worst-case time complexity in skewed tree scenarios; an iterative solution helps.

Duplicate values in 'to_delete' list

How to Handle:

Treat the 'to_delete' list as a set to avoid unnecessary repeated lookups during node deletion.

Deleting the root node

How to Handle:

Handle the root node deletion specifically, adding its children to the result if they are not also being deleted.

'to_delete' contains values not present in the tree

How to Handle:

The algorithm should handle gracefully by simply ignoring these values in the to_delete array during the traversal process.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `node.val` in the tree?
Can the `to_delete` array contain duplicate values?
Can the `to_delete` array be empty, or can it contain values that are not present in the tree?
In the resulting forest, is there a specific ordering required for the trees?
If a node is deleted and has both left and right children, should both children be added to the forest (assuming they aren't in `to_delete`)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, look at each node in the tree individually.
For each node, imagine deleting it from the tree.
When you delete a node, you might create separate, smaller trees (a forest).
Record the roots of these new smaller trees.
After considering deleting each node individually, then try deleting every possible combination of two nodes.
Repeat this process for all possible combinations of nodes: three nodes, four nodes, and so on, up to deleting all the nodes.
For each combination of deleted nodes, identify the roots of the remaining trees.
From all these possible forests that you have generated, return the one that corresponds to exactly deleting the nodes specified in the 'to delete' list.

Code Implementation

def delete_nodes_and_return_forest_brute_force(root, to_delete):
    all_possible_forests = []

    def get_forest_roots(node, current_deleted_nodes):
        if node is None:
            return []

        forest_roots = []
        
        if node.val not in current_deleted_nodes:
            is_root = True
            
            #Check if the node is a root by iterating through every node in the tree
            #to see if current node is a child of a deleted node.
            def check_if_child(potential_parent, node_val):
                if potential_parent is None:
                    return False
                if potential_parent.left and potential_parent.left.val == node_val:
                    return True
                if potential_parent.right and potential_parent.right.val == node_val:
                    return True
                return check_if_child(potential_parent.left, node_val) or check_if_child(potential_parent.right, node_val)

            #If any of the nodes in the tree has current node as a child node then it's not a root
            def is_actually_a_root(root_node):
                #Iterate through every node in the tree
                def helper(node):
                    if node is None:
                        return False
                    if node.val in current_deleted_nodes and check_if_child(node, root_node.val):
                        return True
                    return helper(node.left) or helper(node.right)
                
                # Call helper from the tree root
                return not helper(root)

            if is_actually_a_root(node):
                forest_roots.append(node)

        forest_roots.extend(get_forest_roots(node.left, current_deleted_nodes))
        forest_roots.extend(get_forest_roots(node.right, current_deleted_nodes))

        return forest_roots

    # Generate all possible combinations of nodes to delete
    number_of_nodes = 0
    def count_nodes(node):
        nonlocal number_of_nodes
        if not node: return
        number_of_nodes += 1
        count_nodes(node.left)
        count_nodes(node.right)
    count_nodes(root)

    for i in range(1 << number_of_nodes):
        current_deleted_nodes = []
        all_nodes_list = []
        
        # Extract all nodes from the tree into a list to iterate
        def get_all_nodes(node):
            if node is None:
                return
            all_nodes_list.append(node.val)
            get_all_nodes(node.left)
            get_all_nodes(node.right)
        get_all_nodes(root)

        # Find the nodes that are going to be deleted in current iteration
        for j in range(number_of_nodes):
            if (i >> j) & 1:
                current_deleted_nodes.append(all_nodes_list[j])

        # Now we extract the forest by passing the current nodes to delete
        forest = get_forest_roots(root, current_deleted_nodes)
        all_possible_forests.append((current_deleted_nodes, forest))

    # Find the forest that corresponds to exactly deleting the nodes in 'to_delete'
    for deleted_nodes, forest in all_possible_forests:
        if sorted(deleted_nodes) == sorted(to_delete):
            #The combination of nodes to delete matches to_delete, returning the forest
            return forest

    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, make a list of the values that we want to delete from the tree.
Think of the entire tree as a single forest at the beginning.
Go through each node in the tree, starting from the root.
When you find a node that needs to be deleted:
Remove it from its parent. If it had a parent, then the parent is now the root of a new tree in our forest.
Add the deleted node's children to the forest as separate trees, if they exist. Each child now becomes the root of a new tree.
Keep doing this for every node in the tree.
After you have processed all the nodes, return the list of root nodes in your forest. This will be all the roots from the original tree, plus any roots from the deleted node's children.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def delete_nodes_and_return_forest(root, to_delete):
    nodes_to_delete_set = set(to_delete)
    forest = []

    def helper(node, is_root):
        if not node:
            return None

        # Traverse subtrees first
        node_should_be_deleted = node.value in nodes_to_delete_set
        node.left = helper(node.left, node_should_be_deleted)
        node.right = helper(node.right, node_should_be_deleted)

        # If the current node needs to be deleted
        if node_should_be_deleted:
            # Add children to the forest
            if node.left:
                forest.append(node.left)
            if node.right:
                forest.append(node.right)
            return None

        # If the current node is a root and not deleted, add to forest
        if is_root:
            forest.append(node)
        return node

    helper(root, True)

    return forest

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root	If the root is null, return an empty list because there's no tree to process.
Empty 'to_delete' list	If 'to_delete' is empty, return a list containing only the root node.
All nodes need to be deleted	If all nodes are in 'to_delete', return an empty list indicating no forest remains.
Large tree and large 'to_delete' list causing recursion depth issues	The solution should be iterative or use a tree traversal approach to avoid stack overflow errors.
Tree is skewed heavily to one side (left or right)	Ensure the algorithm doesn't exhibit worst-case time complexity in skewed tree scenarios; an iterative solution helps.
Duplicate values in 'to_delete' list	Treat the 'to_delete' list as a set to avoid unnecessary repeated lookups during node deletion.
Deleting the root node	Handle the root node deletion specifically, adding its children to the result if they are not also being deleted.
'to_delete' contains values not present in the tree	The algorithm should handle gracefully by simply ignoring these values in the to_delete array during the traversal process.

Null root

How to Handle:

If the root is null, return an empty list because there's no tree to process.

Empty 'to_delete' list

How to Handle:

If 'to_delete' is empty, return a list containing only the root node.

All nodes need to be deleted

How to Handle:

If all nodes are in 'to_delete', return an empty list indicating no forest remains.

Large tree and large 'to_delete' list causing recursion depth issues

How to Handle:

The solution should be iterative or use a tree traversal approach to avoid stack overflow errors.

Tree is skewed heavily to one side (left or right)

How to Handle:

Ensure the algorithm doesn't exhibit worst-case time complexity in skewed tree scenarios; an iterative solution helps.

Duplicate values in 'to_delete' list

How to Handle:

Treat the 'to_delete' list as a set to avoid unnecessary repeated lookups during node deletion.

Deleting the root node

How to Handle:

Handle the root node deletion specifically, adding its children to the result if they are not also being deleted.

'to_delete' contains values not present in the tree

How to Handle:

The algorithm should handle gracefully by simply ignoring these values in the to_delete array during the traversal process.