How to calculate the depth of a binary search tree

Question

I would like to calculate the summation of the depths of each node of a Binary Search Tree.

The individual depths of the elements are not already stored.

Magnum

Changing the question after people have supplied answers is going to make the original answers seem unrelated to the latest question. Also you can't Accept two answers. Would be better to ask a new question, i.e. on a new page. You might also want to Accept an answer to the original question. – Psychro

Answer 1

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

Zingale

I would like to note that Kyle is referring to my first function and not the explanation which was added later and is of dubious quality. – Zingale

Answer 2

int maxDepth(Node node) {
    if (node == null) {
        return (-1); // an empty tree  has height −1
    } else {
        // compute the depth of each subtree
        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);
        // use the larger one
        if (leftDepth > rightDepth )
            return (leftDepth + 1);
        else
            return (rightDepth + 1);
    }
}

Collete

why +1 in return? – Dais

Because you have traversed a layer and going into the next. Without +1 you will always get zero as max depth. – Comforter

Don't we need to initialize leftDepth and rightDepth to zero before starting to count? – Rapscallion

Answer 3

This solution is even more simpler.

public int getHeight(Node root)
{
    if(root!=null)
        return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild));
    else
        return 0;
}

Vicenary

Answer 4

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".

Batty

Carl is right. the easiest way to do this is: public int countNodes(Node root) { if(root == null) return 0; return 1 + countNodes(root.getLeft()) + countNodes(root.getRight()); } – Calcutta

Original poster: That doesn't help me actually do it :P. Read the question, I have difficulty retaining a sum in a recursive method for the number of nodes while traversing the BST. – Magnum

You don't need to retain anything, as Gennadiy demonstrated above. – Haemostat

You don't have to retain a sum. All you need to do is find the sum of up to 3 numbers and return that to your caller. – Batty

Answer 5

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

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

Forman

Answer 6

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;
}

Mcgregor

Answer 7

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

Karrykarst

Answer 8

int depth(treenode *p)
{
   if(p==NULL)return(0);
   if(p->left){h1=depth(p->left);}
   if(p=>right){h2=depth(p->right);}
   return(max(h1,h2)+1);
}

Terpstra

Answer 9

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;
}

Racialism

Answer 10

public int getDepthHelper( TreeNode< T > node ) { 
    int treeHeightLeft; 
    int treeHeightRight; 
    //get height of left subtree 
    if( node.leftNode == null ) 
        treeHeightLeft = 1; 
    else { 
        treeHeightLeft = getDepthHelper( node.leftNode) + 1; 
    } 

    //get height of right subtree 
    if( node.rightNode == null ) 
        treeHeightRight = 1; 
    else { 
        treeHeightRight = getDepthHelper( node.rightNode) + 1; 
    } 
    return Math.max(treeHeightLeft, treeHeightRight); 
}

Fastidious