# find depth of binary search tree

May 2, 2013 3 Comments

We can find the depth of the binary search tree in **three different recursive ways**

– using instance variables to record current depth and total depth at every level

– without using instance variables in top-bottom approach

– without using instance variables in bottom-up approach

Full source code can be **downloaded here **

**Approach #1: using instance variables to record current depth and total depth at every level**

int currentDepth, depth; public int depth(BinaryNode n) { if (n != null) { currentDepth++; // record total depth if current depth is greater than total depth if (currentDepth > depth) { depth = currentDepth; } // recursively traverse entire tree depth(n.left); depth(n.right); // decrement as we traverse up the binary tree currentDepth--; } return depth; }

**Pros**: Easier to implement and understand

**Cons**: Usage of instance variables. Ideally any recursive call should not make use of instance variables and by doing so it moves close towards linear programming.

**Approach #2: without using instance variables in top-bottom approach**

public int depth3(BinaryNode node, int d){ int leftDepth = d, rightDepth = d; if(node.left != null){ leftDepth = depth3(node.left, d+1); } if(node.right != null){ rightDepth = depth3(node.right, d+1); } return leftDepth > rightDepth ? leftDepth : rightDepth; }

**Approach #3: without using instance variables in bottom-up approach**

public int depth2(BinaryNode node){ if(node == null) return 0; int left = depth2(node.left); int right = depth2(node.right); int x = left > right ? left+1 : right+1; return x; }

Approach #2 and #3 are actually recursive way of finding the depth. In #2 we only depend on the return type of the method because back-tracking helps us to keep track of the tree depth. In #3, since we are incrementing the depth in top-bottom fashion, we need additional parameter to the method to track the depth.

My 2 cents for best approach is #2.

Full source code can be **downloaded here **

Output:

Maximum depth of the Binary Tree is using instance variables: 3 Maximum depth of the Binary Tree is without using instance variables in bottom-up approach: 3 Maximum depth of the Binary Tree is without using instance variables in top-bottom approach: 3 | |-------28 |-------25 | |-------22 20 | |-------18 |-------15 | |-------12

One question: in the piece of code “using instance variables to record current depth and total depth at every level”, shouldn’t be the decrementation just before the call to depth(n.right)?

depth(n.left);

currentDepth–;

depth(n.right);

no, its after the left and right recursive calls. It indicates that there are no more nodes down and hence we need to go one level up

determineDepth( TreeNode *ptr, int *totPtr, int *currPtr ) const