Delete subtree from an array of treenodes

Question

I am struggling with a Java exercise.

I am given an array of tree nodes. Each tree node has a parenting, and a int value. I am also given an int, which represents a node value. I am asked to delete the subtree from the array where the value given is the root of the subtree.

I am thinking the best approach might be to create an arraylist, and iterate through the input array, adding the nodes I am keeping to the arraylist, and then convert that arraylist to an array.

I am struggling with determining the best way to delete all of the subtree roots children since I only have parentId.

Am I on the right track?

Answer 1

Here's an algorithm you can use:

1. On the first pass, create a mapping M1 from {parentIdx -> [childIdx1, childIdx2]} and a mapping M2 from {value -> idx}
2. Given the value of the subtree root that you need to remove, find its idx using M2. This is your parentIdx that can be used in M1
3. Do a Depth First Search in M1 starting with parentIdx you found in step (2). Keep a visited set where you record all the child indices you have visited.
4. Now, iterate though the original array and delete the indices you visited as part of step (4)
5. You are golden!

Time complexity = O(n) Space complexity = O(n)

Answer 2

If you're allowed to update Nodes before purging them a simple approach would be to iterate through the array and use a recursive function to follow the path from each node to the root or a parent whose data matches the query data. In the latter case we update the data of all nodes on the path to the query value. Then, in a 2nd pass through the array we compress it, removing nodes whose value matches the query.

Here's some Java code to illustrate:

static int clearPath(Node[] arr, int query)
{
    for(int i=0; i<arr.length; i++)
        if(arr[i].data != query)
            markPath(arr[i], query);
    
    int j = 0;
    for(int i=0; i<arr.length; i++)
        if(arr[i].data != query)
            arr[j++] = arr[i];
    
    return j;
}

static boolean markPath(Node node, int query)
{
    if(node == null) return false;
    
    if(node.data == query) return true;
    
    boolean located = markPath(node.parent, query);
    if(located) node.data = query;
    return located;
}

And the Node class:

static class Node
{
    Node parent;
    int data;
    public Node(Node parent, int data)
    {
        this.parent = parent;
        this.data = data;
    }
    
    public String toString()
    {
        return String.format("(%d : %s) ", data, (parent == null ? "*" : parent.data)); 
    }
}

Test:

int[][] tree = {{1, 2, 3, 4}, {2, 3, 4, 5}, {5, 6, 7}};
List<Node> nodeList = new ArrayList<>();
for(int[] sub : tree)
{
    Node node = null;
    for(int data : sub)
        nodeList.add(node = new Node(node, data));              
}    
Node[] arr = nodeList.toArray(new Node[nodeList.size()]);

System.out.println(Arrays.toString(arr));

int n = clearPath(arr, 3);

System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, n)));

Output:

[(1 : *) , (2 : 1) , (3 : 2) , (4 : 3) , (2 : *) , (3 : 2) , (4 : 3) , (5 : 4) , (5 : *) , (6 : 5) , (7 : 6) ]
[(1 : *) , (2 : 1) , (2 : *) , (5 : *) , (6 : 5) , (7 : 6) ]

If you're not allowed to update node data you could use a Set to hold nodes to be removed.

static int clearPath2(Node[] arr, int query)
{
    Set<Node> rem = new HashSet<>();        
    for(int i=0; i<arr.length; i++)
        markPath2(rem, arr[i], query);

    int j = 0;
    for(int i=0; i<arr.length; i++)
        if(!rem.contains(arr[i])) arr[j++] = arr[i];
    
    return j;
}

static boolean markPath2(Set<Node> rem, Node node, int query)
{
    if(node == null) return false;
    
    if(node.data == query || markPath2(rem, node.parent, query)) 
    {
        rem.add(node);
        return true;
    }
    return false;
}

Answer 3

This solution does not give you the best performance, because it iterates over the given array multiple times, but it's pretty simple.

public class MavenMain {

    public static final class Node {
        private final int id;
        private final Integer parentId;
        private final int val;

        public Node(int id, Integer parentId, int val) {
            this.id = id;
            this.parentId = parentId;
            this.val = val;
        }

    }

    public static void main(String... args) {
        /*
         *          1
         *         / \
         *       2     5
         *      / \   / \
         *     3   4 6   7
         */
        Node[] nodes = {
                new Node(11, null, 1),
                new Node(22, 11, 2), new Node(55, 11, 5),
                new Node(33, 22, 3), new Node(44, 22, 4), new Node(66, 55, 6), new Node(77, 55, 7) };
        Node[] res = removeSubtree(nodes, 1);  // remove root is 2
    }

    public static Node[] removeSubtree(Node[] nodes, int subTreeRoot) {
        Node removeRoot = nodes[subTreeRoot];

        if (removeRoot.parentId == null) // this is a root, i.e. remove whole tree
            return new Node[0];

        Set<Integer> removedNodes = new HashSet<>();
        removedNodes.add(removeRoot.id);

        while (true) {
            boolean found = false;

            for (int i = 0; i < nodes.length; i++) {
                if (removedNodes.contains(nodes[i].id) || !removedNodes.contains(nodes[i].parentId))
                    continue;

                removedNodes.add(nodes[i].id);
                found = true;
            }

            if (!found)
                break;
        }

        Node[] res = new Node[nodes.length - removedNodes.size()];

        for (int i = 0, j = 0; i < nodes.length; i++)
            if (!removedNodes.contains(nodes[i].id))
                res[j++] = nodes[i];

        return res;
    }

}

Answer 4

Are you given the root of the tree nodes? If so just traverse the tree. Once you hit the node value to be deleted, just remove the link of the previous node from the node to be deleted.

This link explains it- Remove Subtree with specific value

Answer 5

Try a treemap instead of the arraylist. Best regards