CODEWITHSUNDEEP
java
William Falcon
William Falcon

Reputation: 9813

Get height of tree with multiple children

I'm having a hard time completing this algorithm to find the height of a tree with multiple children (not binary).

Anyone know where this is going wrong?

private int getHeight(Node<T> root, int height, int result){

        if (root.getChildren().size()==0) {
            return height;
        }
        height++;

        //Iterate every child
        for (Node<T> childNode  : root.getChildren()) {

            //Get the height again
            height =getHeight(childNode, height, result);

            //Update if new high result
            if (height>result) {
                result = height;
            }

            height = 0;
        }

        //Return highest point
        return result;
    }

Upvotes: 0

Views: 3419

Answers (2)

Jsdodgers
Jsdodgers

Reputation: 5312

The way you are calculating the height is very awkward and there are many places for possible errors, such as you adding one to the height then getting the height of the children.

I would suggest doing a simpler recursive function that is similar to the one that you are doing.

First of all, you can get rid of the second and third parameters, then you can change the code to look something more like this:

private int getHeight(Node<T> root){

    if (root.getChildren().size()==0) {
        return 1;
    }

    int height;
    //Iterate every child
    for (Node<T> childNode  : root.getChildren()) {

        //Get the height again
        int childHeight = getHeight(childNode);

        //Update if new high result
        if (childHeight>height) {
            height = childHeight;
        }
    }

    //Return highest point
    return height + 1;
}

This just returns 1 if the node has no children. Otherwise, it gets the max height of all children and returns that number plus 1.

Upvotes: 1

walrii
walrii

Reputation: 3522

You are making it harder by adding the height and result parameters.

In the function, find the height of each of the children. Keep the largest. Return 1 + height of the largest.

Sometrhing like this (untested, uncompiled):

private int getHeight(Node<T> root){

    int max = 0;
    for (Node<T> childNode  : root.getChildren()) {
        int height = getHeight(childNode);
        if (height > max)
            max = height;
    }
    return max + 1;
}

Upvotes: 1

Related Questions