Java Program to Find the Height of a Binary Tree

This Java program demonstrates how to calculate the height of a binary tree. The height or depth of a binary tree is defined as the longest path from the root node to the farthest leaf node. This is an essential metric in many algorithms and applications involving trees, such as balanced tree operations and layer-based traversal techniques.

Binary Tree Class

The BinaryTree class includes the structure of the binary tree nodes and a method to compute the height recursively.

public class BinaryTree {
    static class Node {
        int value;
        Node left, right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    Node root;

    public BinaryTree() {
        root = null;
    }

    // Recursive method to calculate the height of the binary tree
    public int getHeight(Node node) {
        if (node == null) {
            return -1; // Using -1 to denote the height from the node perspective
        } else {
            // Compute the depth of each subtree
            int leftHeight = getHeight(node.left);
            int rightHeight = getHeight(node.right);

            // Use the larger one and add the root
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("The height of the binary tree is:");
        int height = tree.getHeight(tree.root);
        System.out.println(height);
    }
}

Explanation of the getHeight Method

• The method is recursive, with the base case being when the node is null, in which case it returns -1, signifying the height below the lowest leaf node.
• It recursively calculates the height of the left and right subtrees, then returns the greater of the two heights plus one (to account for the current node).

Conclusion

Computing the height of a binary tree is crucial for understanding its structure and complexity. This Java implementation offers a clear and efficient method for determining the tree’s height, which is essential for various applications in computer science and software engineering.