Getting a height of a binary tree with no function parameters

Question

import java.util.Scanner;

public class BinaryTree {

private int info;
private BinaryTree left;
private BinaryTree right;
private int height = 1;

public BinaryTree()
{
    left = null;
    right = null;
}

public BinaryTree(int theInfo)
{
    Scanner sc = new Scanner(System.in);
    int intNum;
    String s;

    info = theInfo;

    System.out.print("Does the node " + info + " have a left child (y or n)? ");
    s = sc.next();
    if (s.equals("y"))
    {
        System.out.print ("What value should go in the left child node? ");
        intNum = sc.nextInt();
        left = new BinaryTree(intNum);
    }
    System.out.print("Does the node " + info + " have a right child (y or n)? ");
    s = sc.next();
    if (s.equals("y"))
    {
        System.out.print ("What value should go in the right child node? ");
        intNum = sc.nextInt();
        right = new BinaryTree(intNum);
    }
}

int heightLeft = 0;
int heightRight = 0;


public int getHeight()
{
    int counterOld = 0;
    int counter = 0;
     if (left != null)
    {
        counter++;

        if (counter > counterOld)
        {   
            counterOld = counter;
        }
        counter += left.getHeight();
    }
    if (left == null)
    {    System.out.println("counter is: " + counter + " and counterOld is: " + counterOld);
        /*if (counter > counterOld)
        {   
            counterOld = counter;
        } */
        counter = 0;

    }
    if (right != null)
    {  
        counter++;
        if (counter > counterOld)
        {
          counterOld = counter;
        }

        counter += right.getHeight();
    }
    if (right == null)
    {  System.out.println("counter is" + counter + " and counterOld is: " + counterOld);
        /*if (counter > counterOld)
        {
          counterOld = counter;
        } */
      counter = 0;

    }
    return counterOld;
 }
}

---

import java.util.Scanner;

public class BinaryTester {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub

    BinaryTree myTree;
    Scanner sc = new Scanner(System.in);
    int intNum;

    System.out.print("What value should go in the root? ");
    intNum = sc.nextInt();
    myTree = new BinaryTree(intNum);
    System.out.println("Height is " + myTree.getHeight());
}
}

---

    400
    /
   300
   /
  200
  /
100

I'm having mixed results with a tree height function counter. I'd like to count how low the tree is down based on the lowest node. For example the tree up above should be a height of 3 with the root being counted at 0. I get the incorrect result of height 1. I get correct results if I input a tree such as this:

      400
    /    \
   300    10
   /     /   \
 100    4    5
        /
       3

This tree will give me a height of 3 which is what I was looking for. Anyone know how I can tweak my code to account for all trees?

Answer 1

Though there is an accepted answer, I would want to give a slightly different alternative.

I think such method is better to be an instance method instead (Shouldn't we try to use OOP paradigm as we are using Java? ;P )

code looks like:

class BinaryTree {
    private BinaryTree left, right;
    int getHeight() {
        if (left == null && right == null) {
            return 0;
        } else {
            int leftHeight = (left==null? 0: left.getHeight());
            int rightHeight = (right==null? 0: right.getHeight());
            return Math.max(leftHeight ,rightHeight) + 1;
        }
        // whole method can even shrink to one-line like
        // return Math.max((left==null? -1: left.getHeight()),
        //                 (right==null? -1: right.getHeight()))
        //          + 1;
    }
}

It is, imho, more intuitive when using it:

BinaryTree tree = ....;
int height = tree.getHeight();

(and it gives you 0-based tree height ;P )

Answer 2

recursion is a lot easier when working with trees.

public int getHeight(BinaryTree node){
    if(node == null){
        return 0;
    }

    int left = getHeight(node.left);
    int right = getHeight(node.right);

    return Math.max(left, right) + 1;
}

This method gives a one-based height. If you want to start the count at zero then you can subtract one from it, e.g.

getHeight(tree) - 1