Find maximum height or depth of binary tree. (Java Code)

Problem : Find the height of binary tree where tree might or might be complete .

Observations :

For complete BST

height = at most log2(total number of nodes)

or

h = long2(n)

So it is straight forward no traversal is needed , But if tree is not complete then we need to find height of all the leaves   and get maximum out of it .

We need to store only max value at any given time . Means we do not need caching of heights for each leaf..
We need to use depth first recursion as we need to calculate depth or height .

Algorithm Class : Recursion - back tracking


Java Code

package com.salpe.tree;

import java.util.logging.Logger;

import org.junit.Test;

/**
 * Find maximum height/depth of binary tree
 * Algorithm will be same for binary tree or binary search tree.
 */
public class BSTTest3 {

 // logger
 private static final Logger s_logger = Logger.getLogger(BSTTest2.class.getName());

 /**
  * Binary search tree pre-order list as 0,1,2,3,4,5,6
  */
 @Test
 public void test() {

  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);

  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);

  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);

  int maxHeight = bst.findMaxHeight();

  s_logger.info(Integer.toString(maxHeight));

 }

 /**
  * Binary Tree Node model
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  T data;
  BSTNode<T> left;
  BSTNode<T> right;

  BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {

   this.data = data;
   this.left = left;
   this.right = right;

  }

  @Override
  public String toString() {
   return "BSTNode [data=" + data + "]";
  }

 }

 /**
  * Binary Tree Representation
  *
  * @param <T>
  */
 static class BST<T extends Comparable<T>> {

  BSTNode<T> root;

  public BST(BSTNode<T> root) {
   this.root = root;
  }

  /**
   * @return max height or max depth of balanced or unbalanced binary
   *         tree.
   */
  public int findMaxHeight() {

   return depthFirstSearch0(root, 0);

  }

  /**
   * Need to traverse all tree because right/left most side might be max
   * length problem could be solved using dynamic programming also by
   * caching latest maximum height
   * 
   * @param node
   *            - root
   * @param currentHeight
   * @return maximum height of binary search tree.
   */
  public int depthFirstSearch0(BSTNode<T> node, int currentHeight) {

   if (node == null) {

    return currentHeight;
   }

   // increase height by 1 for increase in depth for recursion stack
   currentHeight++;

   // go left
   int leftMaxHeight = depthFirstSearch0(node.left, currentHeight);
   // then go right
   int rightMaxheight = depthFirstSearch0(node.right, currentHeight);

   // decrease height by 1 for decrease in depth for recursion stack
   currentHeight--;

   return Math.max(leftMaxHeight, rightMaxheight);

  }

 }

}