Find Height of a Binary Tree - Visualization

Visualization Player

Problem Statement

Given the root node of a binary tree, determine its height. The height (or maximum depth) of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node.

Examples

Input Tree Height Description
[1, 2, 3, 4, 5, null, 6]
3 Standard tree with three levels including missing children
[1]
1 Single-node tree has height 1
[] 0 Empty tree has height 0
[1, 2, null, 3, null, null, null, 4]
4 Left-skewed tree with 4 nodes in depth
[1, null, 2, null, null, null, 3]
3 Right-skewed tree with height 3
[5, 3, 8, 1, 4, 7, 9]
3 Complete binary tree with 3 levels

Solution

Understanding the Problem

We are given a binary tree, and our task is to find its height. But what does "height" mean here?

The height of a binary tree is defined as the number of edges on the longest path from the root node down to the farthest leaf node. Some people define it in terms of the number of nodes (in that case, it's the number of nodes on the longest path). We'll use the number of nodes convention here, meaning the height of a tree with only the root node is 1.

We’ll now walk through a simple and intuitive example and build our understanding step by step.

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Consider the binary tree represented like this:


       1
      /      2   3
    /
   4

This tree has the following structure:

  • Root node is 1
  • Node 1 has two children: 2 (left) and 3 (right)
  • Node 2 has one child: 4 (left)
  • Nodes 3 and 4 are leaf nodes (no children)

Step 2: Use Recursion to Compute Height

We’ll calculate the height recursively:

  • Start at the root node (1)
  • Recursively compute the height of left subtree (node 2 → 4)
  • Recursively compute the height of right subtree (node 3)
  • Take the maximum of the two, and add 1 (for the current node)

So:

  • Height of node 4 = 1 (leaf)
  • Height of node 2 = 1 + height of node 4 = 2
  • Height of node 3 = 1 (leaf)
  • Height of root node (1) = 1 + max(2, 1) = 3

Final height = 3

Step 3: Implement the Recursive Function

public int height(TreeNode root) {
    if (root == null) return 0;
    int left = height(root.left);
    int right = height(root.right);
    return 1 + Math.max(left, right);
}

Edge Cases

Case 1: Empty Tree

If the root node is null, then the tree is empty and its height is 0.

Case 2: Tree with Only One Node

Height is 1 since only the root exists.

Case 3: Left-Skewed Tree


    1
   /
  2
 /
3

Each node has only a left child. The height equals the number of nodes: 3.

Case 4: Right-Skewed Tree


1
   2
       3

Each node has only a right child. The height is also 3.

Case 5: Balanced Tree


    1
   /   2   3
 / 4   5

This tree has 3 levels, so the height is 3.

Finally

Calculating the height of a binary tree is one of the most common and foundational problems in tree data structures. Once you understand the recursive nature of trees, this problem becomes intuitive. Always consider edge cases like empty trees, skewed trees, and single-node trees while designing your solution.

As a beginner, remember: recursion often mirrors the structure of the tree itself. Think of each node as its own mini-tree asking, “What’s the height of my children?”

Algorithm Steps

  1. If the tree is empty, the height is 0.
  2. Recursively compute the height of the left subtree.
  3. Recursively compute the height of the right subtree.
  4. The height of the tree is 1 + max(height(left), height(right)).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int findHeight(TreeNode* root) {
    if (root == NULL) return 0;
    int leftHeight = findHeight(root->left);
    int rightHeight = findHeight(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Height of the tree: %d\n", findHeight(root));
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...