Calculate the DEPTH of a binary search tree?

Question

Original problem: Calculate the number of nodes [SOLVED].

---

I have another similar problem, and both of these have been killing me for a while now.

I can calculate the number of words fine now. Thank you very much for your assistance.

The issue is now calculating the summation of depths [the sum of the individual depths for all children of the root] for this BST. The individual depths of the elements are not already stored.

The reason I need the number of nodes and this summation is I am trying to calculate the average depth of this BST.

Answer 1

For any given tree, the number of nodes is 1 for the root plus the number of nodes in the left subtree plus the number of nodes in the right subtree :)

Details, like making sure there actually is a left or right subtree, are "left to the reader".

Answer 2

Something like this:

int countChildren(Node node)
{
    if ( node == null )
        return 0;
    return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}

And to get the sum of the depths of every child:

int sumDepthOfAllChildren(Node node, int depth)
{
    if ( node == null )
        return 0;  // starting to see a pattern?
    return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + 
                   sumDepthOfAllChildren(node.getRight(), depth + 1);
}

Now for a hopefully informative explanation in case this is homework. Counting the number of nodes is quite simple. First of all, if the node isn't a node (node == null) it returns 0. If it is a node, it first counts its self (the 1), plus the number of nodes in its left sub-tree plus the number of nodes in its right sub-tree. Another way to think of it is you visit every node via BFS, and add one to the count for every node you visit.

The Summation of depths is similar, except instead of adding just one for each node, the node adds the depth of its self. And it knows the depth of its self because its parent told it. Each node knows that the depth of it's children are it's own depth plus one, so when you get the depth of the left and right children of a node, you tell them their depth is the current node's depth plus 1.

And again, if the node isn't a node, it has no depth. So if you want the sum of the depth of all the root node's children, you pass in the root node and the root node's depth like so: sumDepthOfAllChildren(root, 0)

Recursion is quite useful, it's just a very different way of thinking about things and takes practice to get accustomed to it

Answer 3

public int numberOfNodes()
{
   // This node.
   int result = 1;

   // Plus all the nodes from the left node.
   Node left = getLeft();
   if (left != null)
       result += left.numberOfNodes();

   // Plus all the nodes from the right node.
   Node right = getRight();
   if (right != null)
       result += right.numberOfNodes();

   return result;
}

Answer 4

public int countNodes(Node root)
{  
   // Setup
   // assign to temps to avoid double call accessors. 
   Node left = root.getLeft();
   Node right = root.getRight();
   int count = 1; // count THIS node.

   // count subtrees
   if (left != null) count += countNodes(left);
   if (right != null) count += countNodes(right);

   return count;
}

Answer 5

public class Node {
   private Node left; 
   private Node right;
   public int size() { return 1+ (left==null?0:left.size())+ (right==null?0:right.size());}
}

Answer 6

I have another similar problem, and both of these have been killing me for a while now.

I can calculate the number of words fine now. Thank you very much for your assistance.

The issue is now calculating the summation of depths [the sum of the individual depths for all children of the root] for this BST. The individual depths of the elements are not already stored.

The reason I need the number of nodes and this summation is I am trying to calculate the average depth of this BST.

Thank you for any assistance you can provide.

Answer 7

private static int getNumberOfNodes(Node node) {
    if (node == null) {
        return 0;
    }

    return 1 + getNumberOfNodes(node.left) + getNumberOfNodes(node.right);
}