Find Height of a Binary Tree

Problem and examples

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.

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

Explore Find Height of a Binary Tree

Load an example or enter your own input. Use the player controls to follow each change.

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

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?”

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

int findHeight(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(findHeight(root->left), findHeight(root->right));
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << "Height of the tree: " << findHeight(root) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findHeight(root):
    if not root:
        return 0
    return 1 + max(findHeight(root.left), findHeight(root.right))

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("Height of the tree:", findHeight(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
    }
}

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        BinaryTreeHeight sol = new BinaryTreeHeight();
        System.out.println("Height of the tree: " + sol.findHeight(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findHeight(root) {
    if (!root) return 0;
    return 1 + Math.max(findHeight(root.left), findHeight(root.right));
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log("Height of the tree:", findHeight(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func findHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := findHeight(root.left)
    rightHeight := findHeight(root.right)
    if leftHeight > rightHeight {
        return 1 + leftHeight
    }
    return 1 + rightHeight
}

func main() {
    root := &TreeNode{val: 1}
    root.left = &TreeNode{val: 2}
    root.right = &TreeNode{val: 3}
    root.left.left = &TreeNode{val: 4}
    root.left.right = &TreeNode{val: 5}
    fmt.Println("Height of the tree:", findHeight(root))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn find_height(root: &Option<Box<TreeNode>>) -> i32 {
    if let Some(node) = root {
        let lh = find_height(&node.left);
        let rh = find_height(&node.right);
        1 + lh.max(rh)
    } else {
        0
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode::new(4))),
            right: Some(Box::new(TreeNode::new(5))),
        })),
        right: Some(Box::new(TreeNode::new(3))),
    }));

    println!("Height of the tree: {}", find_height(&root));
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun findHeight(root: TreeNode?): Int {
    if (root == null) return 0
    return 1 + maxOf(findHeight(root.left), findHeight(root.right))
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left!!.left = TreeNode(4)
    root.left!!.right = TreeNode(5)
    println("Height of the tree: ${findHeight(root)}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func findHeight(_ root: TreeNode?) -> Int {
    guard let node = root else { return 0 }
    return 1 + max(findHeight(node.left), findHeight(node.right))
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
print("Height of the tree: \(findHeight(root))")

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findHeight(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(findHeight(root.left), findHeight(root.right));
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log("Height of the tree:", findHeight(root));