John John - 25 days ago 9
Java Question

Getting a height of a binary tree with no function parameters

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?

jb. jb.
Answer

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
Comments