Calculate the depth of a binary search tree?

Question

I am having difficulty calculating the summation of depths [the sum of the individual depths for all children of the root] for a given BST. I have the total number of nodes for the tree, and I am trying to calculate the average depth for the tree, requiring I have this depth sum.

Recursion and I don't get along very well.. I am finding this problem very difficult. I would like to see a recursive solution though, if possible.

NOTE:

I have created accessors Node.getLeft() and Node.getRight()

Answer 1

Think about how you would go about this canonically by hand if I had presented a picture of a BST to you on a sheet of paper. When you're at a node, what information do you need to keep track of? How does one find the height of a given node?

From here, try to translate this into pseudocode or even straight into Java. If you're having trouble, feel free to comment so users can help you out.

Answer 2

You just need to keep a depth counter as you traverse the tree (look up tree traversals if you have to) and add the value of the counter every time you reach a node. Then just divide by the number of nodes.

This looks like homework so I'm not providing a more detailed solution.

Answer 3

Is this homework? If so tag the question as such.

You could create a method that:

• has a node reference and a depth as arguments
• increment depth
• if node is not a child node call recursively for left and right and update sum accordingly
• otherwise return sum + depth

Once you have this devide by the number of children in the tree to get the average depth.

Answer 4

It is homework I'm just bogged down with finals. I've done 99% of it, this is literally the last part I have to implement. Thank you for your assistance, I am sure I can figure it out, was trying to save some time so I could study more for my final tomorrow.

Answer 5

We need to visit all leaf nodes and figure out how deep they are. This suggests:

Give your node-visiting function an extra argument. It needs to know not just where it's going but also how deep it is. Every time it's called, it's called on to go deeper, so your node visitor just has to increment the depth number it got from the caller.

Now one of 2 things can happen:

• Either the node you found is a leaf node, i.e. it doesn't have any children; in this case, your visitor needs to return its depth to the caller. Yeah, it just returns the number it got from the caller, + 1.

• or it's not a leaf node. In that case, it will have either 1 or 2 children. We need to get those depth reports from our kids back up to the caller, so just return the sum of the depths returned by the children.

By the magic of recursion, the number returned to the root's visitor will be the sum of the depths of all children.

To get an average depth, you'll want to divide this by the number of leaf nodes; which I'd leave to a second traversal to calculate. It could be done in one, but it would be a little more complicated.

Answer 6

Since this is homework, I don't want to just give you an answer. Instead, here's a recursive way to calculate the length of a singly linked list. Hopefully this will demonstrate recursion in a way you can understand, and you can extrapolate from there to solve your BST problem.

public final class LL {
    public final int value;
    public LL next;

    public LL(final int value) {
        this.value = value;
    }

    public void add(final int value) {
        if (null == next) {
            next = new LL(value);
        } else {
            next.add(value);
        }
    }

    /**
     * Calculate the length of the linked list with this node as its head (includes this node in the count).
     *
     * @return the length.
     */
    public int length() {
        if (null == next) {
            return 1;
        }
        return 1 + next.length();
    }

    public static void main(final String... args) {
        final LL head = new LL(1);
        head.add(2);
        head.add(3);
        System.out.println(head.length());
        System.out.println(head.next.length());
    }
}