The Height of a Binary Tree in Java

Save

Efficient data structures optimize a program's performance by making it easier for the program to find the data that it needs. Binary search trees are one of the most efficient data structures for searching through an ordered data set. Whether your data structure is an organized binary-search tree or a standard binary tree, you can find the tree's height in Java through a simple recursive function.

Tree Structure

  • A binary tree consists of a set of interconnected nodes. Each node has between zero and two child nodes. Each node with the exception of the root node has exactly one parent node. The root node has no parent nodes. Java does not have a built-in binary tree class, but you can create your own from scratch or download one from the Internet.

Tree Height

  • The height of a binary tree is the maximum number of nodes, not including the root node, along a single vertical traversal through the binary tree. For example, a binary tree with only one node would have a height of zero. A binary tree with one root node with two child nodes would have a height of one. If one of those child nodes had its own child node, the tree would have a height of three.

Theory

  • The simplest way to determine the height of a binary tree in Java is with a recursive method. This method accepts a single node as an argument and returns the height of the binary tree below the argument node. The method calls itself again for each of the argument node's child nodes and stores the result as an integer variable. It compares the two variables, which represent the height of each of its children, adds one to the larger of the two variables and returns the result. If the argument node passed into the method is null, the method returns negative one.

Algorithm

  • The following Java method will calculate the height of a binary tree. It accepts the root node of a binary tree as an argument. Alternatively, you could pass a different node of the binary tree into the method to find the height of the tree below that node. The following code assumes that each node of the binary tree is of the type "BinaryTreeNode" and each node contains methods that return the left and right children of that node called "getLeftChild" and "getRightChild."

    private int findHeight(BinaryTreeNode currentNode){
    if(currentNode.equals(null)){

      return -1;

    }
    int leftHeight = findHeight(currentNode.getLeftChild());
    int rightHeight = findHeight(currentNode.getRightChild());
    int greatestHeight = Math.max(leftHeight, rightHeight);
    return greatestHeight;
    }

References

Promoted By Zergnet

Comments

Related Searches

Check It Out

Geek Vs Geek: Robot battles, hoverboard drag race, and more

M
Is DIY in your DNA? Become part of our maker community.
Submit Your Work!