Maximum Depth or Height of a Binary Tree

Last Updated : 7 Oct, 2025

Given the root of a binary tree, find the maximum depth of the tree.
The maximum depth or height of the tree is the number of edges in the tree from the root to the deepest node.

Examples:

Input:

Output: 2
Explanation: The longest path from the root node to deepest node has 2 edges.
Input:

Output: 3
Explanation: The longest path from the root (node 1) to deepest leaf (node 6) has 3 edges.

Try it on GfG Practice

Table of Content

[Approach 1] Using Recursion
[Approach 2] Level Order Traversal- O(n) Time and O(n) Space

[Approach 1] Using Recursion

The idea is to recursively compute the height of the left and right subtrees for each node. The height of the current node is then calculated by 1 + max(leftHeight, rightHeight). The recursion bottoms out when we reach to a null node, which contributes a height of 0.

C++

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node *left;
    Node *right;

    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int height(Node *root) {
    if (root == nullptr)
        return -1;

    // compute the height of left and right subtrees
    int lHeight = height(root->left);
    int rHeight = height(root->right);

    return max(lHeight, rHeight) + 1;
}

int main() {
  
    // Representation of the input tree:
    //     12
    //    /  \
    //   8   18
    //  / \
    // 5   11
    Node *root = new Node(12);
    root->left = new Node(8);
    root->right = new Node(18);
    root->left->left = new Node(5);
    root->left->right = new Node(11);
    
    cout << height(root);
    
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
}; 

int height(struct Node* root) {
    if (root == NULL)
        return -1;

    // compute the height of left and right subtrees
    int lHeight = height(root->left);
    int rHeight = height(root->right);

    return (lHeight > rHeight ? lHeight : rHeight) + 1;
}

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

int main() {
  
    // Representation of the input tree:
    //     12
    //    /  \
    //   8   18
    //  / \
    // 5   11
    struct Node* root = createNode(12);
    root->left = createNode(8);
    root->right = createNode(18);
    root->left->left = createNode(5);
    root->left->right = createNode(11);
    
    printf("%d\n", height(root));
    
    return 0;
}

Java

// Node structure
class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class GfG {
    static int height(Node root) {
        if (root == null)
            return -1;

        // compute the height of left and right subtrees
        int lHeight = height(root.left);
        int rHeight = height(root.right);

        return Math.max(lHeight, rHeight) + 1;
    }

    public static void main(String[] args) {

        // Representation of the input tree:
        //     12
        //    /  \
        //   8   18
        //  / \
        // 5   11
        Node root = new Node(12);
        root.left = new Node(8);
        root.right = new Node(18);
        root.left.left = new Node(5);
        root.left.right = new Node(11);

        System.out.println(height(root));
    }
}

Python

# Node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

def height(root):
    if root is None:
        return -1

    # compute the height of left and right subtrees
    lHeight = height(root.left)
    rHeight = height(root.right)

    return max(lHeight, rHeight) + 1

if __name__ == "__main__":
  
    # Representation of the input tree:
    #     12
    #    /  \
    #   8   18
    #  / \
    # 5   11
    root = Node(12)
    root.left = Node(8)
    root.right = Node(18)
    root.left.left = Node(5)
    root.left.right = Node(11)

    print(height(root))

C#

using System;

// Node structure
class Node {
    public int data;
    public Node left, right;

    public Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class GfG {
    static int height(Node root) {
        if (root == null)
            return -1;

        // compute the height of left and right subtrees
        int lHeight = height(root.left);
        int rHeight = height(root.right);

        return Math.Max(lHeight, rHeight) + 1;
    }

    static void Main(string[] args) {

        // Representation of the input tree:
        //     12
        //    /  \
        //   8   18
        //  / \
        // 5   11
        Node root = new Node(12);
        root.left = new Node(8);
        root.right = new Node(18);
        root.left.left = new Node(5);
        root.left.right = new Node(11);

        Console.WriteLine(height(root));
    }
}

JavaScript

// Node structure
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

function height(root) {
    if (root === null) {
        return -1;
    }

    // compute the height of left and right subtrees
    let lHeight = height(root.left);
    let rHeight = height(root.right);

    return Math.max(lHeight, rHeight) + 1;
}

// Driver Code

// Representation of the input tree:
//     12
//    /  \
//   8   18
//  / \
// 5   11
let root = new Node(12);
root.left = new Node(8);
root.right = new Node(18);
root.left.left = new Node(5);
root.left.right = new Node(11);

console.log(height(root));

Output

Time Complexity: O(n)
Space Complexity: O(n), Recursive stack space

[Approach 2] Level Order Traversal- O(n) Time and O(n) Space

In level order traversal (BFS), we process the tree level by level. At each step, we note the number of nodes in the current level, process exactly those nodes, and enqueue their children. After finishing each level, we increment the depth counter. By the time the queue is empty, the counter reflects the maximum depth or height of the tree.

C++

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

// Node Structure
class Node {
public:
    int data;
    Node *left, *right;
    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int height(Node* root) {
    if (!root) return 0;

    // Initializing a queue to traverse
    // the tree level by level
    queue<Node*> q;
    q.push(root);
    int depth = 0;

    // Loop until the queue is empty
    while (!q.empty()) {
        int levelSize = q.size();

        // Traverse all nodes at the current level
        for (int i = 0; i < levelSize; i++) {
            Node* curr = q.front();
            q.pop();
            // enqueue their child nodes 
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }

        // Increment depth after traversing each level
        depth++;
    }
    return depth - 1;
}

int main() {
  
    // Representation of the input tree:
    //     12
    //    /  \
    //   8   18
    //  / \
    // 5   11
    Node *root = new Node(12);
    root->left = new Node(8);
    root->right = new Node(18);
    root->left->left = new Node(5);
    root->left->right = new Node(11);
    
    cout << height(root);
    
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// Node Structure
struct Node {
    int data;
    struct Node *left, *right;
} 

// Function to create a new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Queue structure
struct Queue {
    Node** arr;
    int front, rear, size, capacity;
} 

// Function to create a queue
Queue* createQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->capacity = capacity;
    q->front = 0;
    q->rear = 0;
    q->size = 0;
    q->arr = (Node**)malloc(capacity * sizeof(Node*));
    return q;
}

int isEmpty(Queue* q) {
    return q->size == 0;
}

void enqueue(Queue* q, Node* node) {
    if (q->size == q->capacity) return;
    q->arr[q->rear] = node;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
}

Node* dequeue(Queue* q) {
    if (isEmpty(q)) return NULL;
    Node* node = q->arr[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return node;
}

int height(Node* root) {
    if (!root) return 0;

    // Initializing a queue to traverse
    // the tree level by level
    Queue* q = createQueue(100); 
    enqueue(q, root);
    int depth = 0;

    // Loop until the queue is empty
    while (!isEmpty(q)) {
        int levelSize = q->size;

        // Traverse all nodes at the current level
        for (int i = 0; i < levelSize; i++) {
            Node* curr = dequeue(q);
            
            // enqueue their child nodes 
            if (curr->left) enqueue(q, curr->left);
            if (curr->right) enqueue(q, curr->right);
        }

        // Increment depth after traversing each level
        depth++;
    }
    return depth - 1;
}

int main() {
  
    // Representation of the input tree:
    //     12
    //    /  \
    //   8   18
    //  / \
    // 5   11
    Node *root = newNode(12);
    root->left = newNode(8);
    root->right = newNode(18);
    root->left->left = newNode(5);
    root->left->right = newNode(11);
    
    printf("%d", height(root));
    
    return 0;
}

Java

import java.util.LinkedList;
import java.util.Queue;

// Node Structure
class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = null;
        right = null;
    }
}

class GfG {
    static int height(Node root) {
        if (root == null) return 0;

        // Initializing a queue to traverse
        // the tree level by level
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        int depth = 0;

        // Loop until the queue is empty
        while (!q.isEmpty()) {
            int levelSize = q.size();

            // Traverse all nodes at the current level
            for (int i = 0; i < levelSize; i++) {
                Node curr = q.poll();

                if (curr.left != null) q.add(curr.left);
                if (curr.right != null) q.add(curr.right);
            }

            // Increment height after traversing each level
            depth++;
        }
        return depth - 1;
    }

    public static void main(String[] args) {

        // Representation of the input tree:
        //     12
        //    /  \
        //   8   18
        //  / \
        // 5   11
        Node root = new Node(12);
        root.left = new Node(8);
        root.right = new Node(18);
        root.left.left = new Node(5);
        root.left.right = new Node(11);

        System.out.println(height(root));
    }
}

Python

from collections import deque

# Node Structure
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def height(root):
    if root is None:
        return 0

    # Initializing a queue to traverse
    # the tree level by level
    q = deque([root])
    depth = 0

    # Loop until the queue is empty
    while q:
        levelSize = len(q)

        # Traverse all nodes at the current level
        for _ in range(levelSize):
            curr = q.popleft()

            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)

        # Increment depth after traversing each level
        depth += 1

    return depth - 1

if __name__ == "__main__":
  
    # Representation of the input tree:
    #     12
    #    /  \
    #   8   18
    #  / \
    # 5   11
    root = Node(12)
    root.left = Node(8)
    root.right = Node(18)
    root.left.left = Node(5)
    root.left.right = Node(11)

    print(height(root))

C#

using System;
using System.Collections.Generic;

// Node Structure
class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {
    static int height(Node root) {
        if (root == null) {
            return 0;
        }

        // Initializing a queue to traverse
        // the tree level by level
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        int depth = 0;

        // Loop until the queue is empty
        while (q.Count > 0) {
            int levelSize = q.Count;

            // Traverse all nodes at the current level
            for (int i = 0; i < levelSize; i++) {
                Node curr = q.Dequeue();

                if (curr.left != null) {
                    q.Enqueue(curr.left);
                }
                if (curr.right != null) {
                    q.Enqueue(curr.right);
                }
            }

            // Increment depth after traversing 
          	// a level
            depth++;
        }
        return depth - 1;
    }

    static void Main(string[] args) {

        // Representation of the input tree:
        //     12
        //    /  \
        //   8   18
        //  / \
        // 5   11
        Node root = new Node(12);
        root.left = new Node(8);
        root.right = new Node(18);
        root.left.left = new Node(5);
        root.left.right = new Node(11);

        Console.WriteLine(height(root));
    }
}

JavaScript

// Node Structure
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function height(root) {
    if (root === null) {
        return 0;
    }

    // Initializing a queue to traverse
    // the tree level by level
    let queue = [root];
    let depth = 0;

    // Loop until the queue is empty
    while (queue.length > 0) {
        let levelSize = queue.length;

        // Traverse all nodes at the current level
        for (let i = 0; i < levelSize; i++) {
            let curr = queue.shift();

            if (curr.left) {
                queue.push(curr.left);
            }
            if (curr.right) {
                queue.push(curr.right);
            }
        }

        // Increment depth after traversing a level
        depth++;	
    }
    return depth - 1;
}

//Driver Code
// Representation of the input tree:
//     12
//    /  \
//   8   18
//  / \
// 5   11
let root = new Node(12);
root.left = new Node(8);
root.right = new Node(18);
root.left.left = new Node(5);
root.left.right = new Node(11);

console.log(height(root));

Output

Comment

Article Tags:

Height of a Tree

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem