Binary Tree: Node frequency count for 0, 1, or 2 children

user_13605870 0
Viewed 579

I have an assignment:

You’re given the root node of a binary tree T. We distinguish between 3 types of nodes in T: nodes with 0 children, nodes with 1 child, and nodes with 2 children. Determine, for each type, the number of nodes in T. Return your result as an integer array of length 3.

I am given a Java file that generates random test cases for this algorithm.

I am only allowed to create one function to do all of this. I am not allowed to pass any additional parameters into the method below. I am also not allowed to make any other modifications outside of the function that I create.

In the file, there is a base case already inserted. I have been told to traverse the tree in post-order, using recursion.

I am aware of the current issues with my code. But I don’t know how to fix them.

My current code is as follows:

private static int[] problem1(Node root) {

    int[] arr = new int[3];

    if (root == null) {
        return new int[] {
            -1, // nodes with 0 children
            -1, // nodes with 1 child
            -1 // nodes with 2 children
        };
    }
    //problem1(root.left);
    //problem1(root.right);

    if (root.left != null && root.right != null) {
        arr[2]++;
        problem1(root.left);
        problem1(root.right);
    } else if (root.left != null && root.right == null) {
        arr[1]++;
        problem1(root.left);
    } else if (root.left == null && root.right != null) {
        arr[1]++;
        problem1(root.right);
    } else {
        arr[0]++;
    }
    return arr;
}

The Node class is defined as:

static class Node {
            public int value;
            public Node left;
            public Node right;
        }
binary-tree algorithm java
2 Answers
class Playground {
    public static void main(String[ ] args) {
        Node root = new Node(1, new Node(2, null, null), new Node(3, null, null));
        int[] counts = problem1(root);
        System.out.println(counts[0]); // 2 node(s) with 0 children
        System.out.println(counts[1]); // 0 node(s) with 1 children
        System.out.println(counts[2]); // 1 node(s) with 2 children
    }

    // recursively count number of childs for each root/node. Post-order 
    // traversing means both left and right node will be traversed before
    // any computations.
    public static int[] problem1(Node root) {
        // always need a base-case to stop recursive call.
        if(root == null) {
            return new int[]{0,0,0};
        }

        // post-order traversing
        int[] leftChildCounts = problem1(root.left);
        int[] rightChildCounts = problem1(root.right);

        int [] counts = new int[]{0,0,0};
        counts[0] = leftChildCounts[0] + rightChildCounts[0];
        counts[1] = leftChildCounts[1] + rightChildCounts[1];
        counts[2] = leftChildCounts[2] + rightChildCounts[2];

        if(root.left == null && root.right == null) {
            counts[0]++;
        } else if(root.left != null && root.right != null) {
            counts[2]++;
        } else {
            counts[1]++;
        }        
        return counts;
    }
}

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value, Node left, Node right) {
        this.value = 0; 
        this.left = left;
        this.right = right;
    }       
}
user_12489130

I think you've come pretty close, the only thing you should fix is handling the array of result.

Currently you create a new arr that is supposed to stored the results for every call of problem1 and its wrong because this new array has nothing to do with previously created arrays.

Consider to create it outside the call of problem1 method. You can always pass it as an additional parameter and "accumulate" the result (there is even a term called "accumulator" for this, so arr will be an accumulator).

Think also about the return result (hint: with the accumulator approach you don't really need to return anything)

Since its an assignment, obviously I won't give a full solution leaving to you all the fun ;)

user_6051530
Related