Binary Tree Height — How to Calculate Tree Depth

Calculating Binary Tree Height

The height of a binary tree is the number of edges on the longest path from the root to a leaf node. An empty tree has height 0, and a single-node tree has height 1 (when counting nodes) or 0 (when counting edges). Different textbooks use different conventions; here we count nodes on the longest path.

Recursive Formula

HEIGHT(node):
  if node is NULL: return 0
  left_height  = HEIGHT(node.left)
  right_height = HEIGHT(node.right)
  return 1 + max(left_height, right_height)

Example

        4          Height = 3
       / \
      2   6        Height of left subtree = 2
     /             Height of right subtree = 1
    1

HEIGHT(4) = 1 + max(HEIGHT(2), HEIGHT(6))
          = 1 + max(2, 1)
          = 3

Height vs Depth vs Level

These terms are often confused:

Term	Definition
Height of a node	Longest path from that node down to a leaf
Depth of a node	Path length from the root down to that node
Level	Depth + 1 (root is level 1)
Height of the tree	Height of the root node

Iterative Approach Using BFS

You can compute height iteratively using level-order traversal — the number of levels equals the height:

HEIGHT_ITERATIVE(root):
  if root is NULL: return 0
  queue = [root]
  height = 0
  while queue is not empty:
    level_size = queue.size()
    for i in range(level_size):
      node = queue.dequeue()
      if node.left:  queue.enqueue(node.left)
      if node.right: queue.enqueue(node.right)
    height += 1
  return height

Impact on Performance

Tree height directly determines the worst-case time complexity of BST operations (search, insert, delete). A balanced tree has height O(log n), while a degenerate tree has height O(n). This is why self-balancing trees (AVL, Red-Black) are important.