Height of a Binary Tree

Given a binary tree, the task is to find the height of the tree. The height of a binary tree is the number of edges on the longest path from the root node to any leaf node. If a tree has only one node (the root), its height is 0. For an empty tree, the height is -1.

Input/Output Examples

Example 1:

Input:

plaintext

Output: 2
- Explanation: The longest path is from the root (node 1) to node 4 or 5, and the number of edges is 2.

Example 2:

Input:

plaintext

Output: 2
- Explanation: The longest path is from the root (node 10) to node 40, and the number of edges is 2.

Approach to find the Height of a Binary Tree

Recursive Approach:
- The height of a binary tree can be found by recursively calculating the height of the left and right subtrees.
- The height of the tree is the maximum height between the left and right subtrees, plus 1 for the current node.
Base Case: If the node is None (i.e., an empty tree or a leaf node's child), the height is -1.
Recursion: For each node, calculate the height of the left and right subtrees and return the larger of the two plus one.

C++ Program to find the Height of a Binary Tree

cpp

#include <iostream>
using namespace std;

// A binary tree node
struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

// Function to find the height of the binary tree
int height(Node* root) {
    if (root == NULL) {
        return -1; // Base case: height of empty tree is -1
    }
    
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    
    return max(leftHeight, rightHeight) + 1; // Add 1 to account for the current node
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    cout << "The height of the binary tree is: " << height(root) << endl;
    return 0;
}

Java Program to find the Height of a Binary Tree

java

// Class for a binary tree node
class Node {
    int data;
    Node left, right;
    
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;
    
    // Function to find the height of the binary tree
    public int height(Node root) {
        if (root == null) {
            return -1; // Base case: height of empty tree is -1
        }
        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        
        return Math.max(leftHeight, rightHeight) + 1; // Add 1 to account for the current node
    }
    
    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: " + tree.height(tree.root));
    }
}

Python Program to find the Height of a Binary Tree

python

# A class that represents a node of a binary tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to find the height of the binary tree
def height(root):
    if root is None:
        return -1  # Base case: height of empty tree is -1
    
    left_height = height(root.left)
    right_height = height(root.right)
    
    return max(left_height, right_height) + 1  # Add 1 to account for the current node

# Example usage
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    
    print("The height of the binary tree is:", height(root))

Explanation of Code:

Base Case: If the node is None (i.e., the tree is empty or it is a child of a leaf node), the function returns -1 (the height of an empty tree).
Recursion: The function recursively calls itself for the left and right subtrees of the current node. It calculates the maximum height between the left and right subtrees and adds 1 to account for the current node.
Return Value: The final result is the height of the tree, which is the number of edges on the longest path from the root to a leaf.

Time Complexity:

O(n): The function visits each node of the tree exactly once, where n is the number of nodes in the tree.

Related Articles