find depth of binary search tree

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