Find Height of a Binary Tree - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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

Visualization Player

Solution❯

Case 1: Empty Tree

If the tree is empty (i.e., the root node is null), it means there are no nodes at all. Therefore, the height is defined to be 0.

Case 2: Single Node Tree

When the tree has only one node (the root), it means there is one level. The height in this case is 1. This is the simplest non-empty binary tree.

Case 3: Left-Skewed Tree

In a left-skewed binary tree, each node has only a left child. This creates a structure similar to a linked list going downwards to the left. For example, in the tree [1, 2, null, 3], the height is 3 because there are three nodes in the longest path from root to leaf (1 → 2 → 3).

Case 4: Right-Skewed Tree

This is the mirror image of the left-skewed case. Each node has only a right child. Like the left-skewed case, the number of nodes along the path determines the height. For [1, null, 2, null, 3], the height is 3 (1 → 2 → 3).

Case 5: Complete or Balanced Tree

In a complete or balanced binary tree like [1, 2, 3, 4, 5], nodes are filled from top to bottom and left to right. The height is determined by the number of levels. Here, the tree has 3 levels, so the height is 3. This is often the best-case structure for performance in many binary tree algorithms.

How Height is Calculated

To compute the height, we use a recursive approach. For each node, we calculate the height of its left and right subtrees. The height of the current node is 1 + max(height(left), height(right)). The recursion continues until we reach null (which returns 0), and the final value returned from the root node gives the height of the whole tree.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("Height of the tree:", findHeight(root))