Height of a Tree

Say you have a tree and someone asks you, “how tall is it?” You cannot just look at it in code. The tree lives in memory as nodes pointing to other nodes. So we need a clear way to measure it. That is what the height of a tree tells us. The good news is the trick to find it is short and clean.

📏 What Does Height Even Mean?

The height of a tree is the length of the longest path from the root all the way down to the deepest leaf. A leaf is a node with no children. The root is the topmost node.

Now the one thing people argue about is how we count that path. You can count edges, or you can count nodes.

• Count the edges on the path. An edge is the line connecting two nodes. With this rule an empty tree has height -1 and a single lonely node has height 0.
• Count the nodes on the path. With this rule an empty tree has height 0 and a single node has height 1.

Both are fine. The only rule is you must pick one and stay with it. In this tutorial we count nodes. So an empty subtree has height 0, and a single node has height 1. We do this because the code comes out very clean.

🌳 A Sample Tree to Work With

Let us picture a small tree so the idea feels real.

Look at the longest path from the root. It goes 1 -> 2 -> 4 or 1 -> 2 -> 5. Both touch 3 nodes. So the height of this tree is 3 when we count nodes. The right branch is 1 -> 3 -> 6. That also has 3 nodes. So that path matches too.

💡 The Simple Recursive Idea

Here is the whole secret in one line. The height of a node is 1 plus the larger of its two children’s heights.

Why does this work? Think about it from one node’s point of view.

• The node itself adds 1 to whatever path goes through it.
• Below it sits a left subtree and a right subtree. Each one has its own height.
• The longest path going down must go through the taller of the two. So we take the bigger child height.
• Add them up and you get this node’s height.

And when do we stop? When the node is empty, that is null. An empty subtree has height 0. That is our base case, the point where the recursion stops calling itself.

🪜 Steps to Find the Height

Let us turn that idea into clear steps before we write any code.

1. If the current node is empty (null), return 0. This is the base case.
2. Call the same function on the left child. Save the answer as the left height.
3. Call the same function on the right child. Save the answer as the right height.
4. Take the larger of the left height and the right height.
5. Add 1 to it for the current node, and return that.

That is the full method. Notice steps 2 and 3 are the function calling itself. That is the recursion doing the heavy work for us.

💻 Computing the Height in Code

Now let us write it in all five languages. Each program builds the same sample tree from above and prints its height. Read the comments along the way.

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

// A single node of the binary tree
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

// Helper to make a new node
struct Node *newNode(int value) {
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Returns the bigger of two numbers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Height counted in nodes; empty tree has height 0
int height(struct Node *node) {
    if (node == NULL) {
        return 0; // base case: empty subtree
    }
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return 1 + max(leftHeight, rightHeight); // 1 for this node
}

int main(void) {
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);

    printf("Height of the tree: %d\n", height(root));
    return 0;
}

Height of the tree: 3

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

// A single node of the binary tree
struct Node {
    int data;
    Node *left;
    Node *right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// Height counted in nodes; empty tree has height 0
int height(Node *node) {
    if (node == nullptr) {
        return 0; // base case: empty subtree
    }
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return 1 + max(leftHeight, rightHeight); // 1 for this node
}

int main() {
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);

    cout << "Height of the tree: " << height(root) << endl;
    return 0;
}

Height of the tree: 3

class Node {
    int data;
    Node left, right;

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

public class Height {
    // Height counted in nodes; empty tree has height 0
    static int height(Node node) {
        if (node == null) {
            return 0; // base case: empty subtree
        }
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        return 1 + Math.max(leftHeight, rightHeight); // 1 for this node
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);

        System.out.println("Height of the tree: " + height(root));
    }
}

Height of the tree: 3

# A single node of the binary tree
class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

# Height counted in nodes; empty tree has height 0
def height(node):
    if node is None:
        return 0  # base case: empty subtree
    left_height = height(node.left)
    right_height = height(node.right)
    return 1 + max(left_height, right_height)  # 1 for this node

# Build the sample tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

print("Height of the tree:", height(root))

Height of the tree: 3

// A single node of the binary tree
class Node {
  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}

// Height counted in nodes; empty tree has height 0
function height(node) {
  if (node === null) {
    return 0; // base case: empty subtree
  }
  const leftHeight = height(node.left);
  const rightHeight = height(node.right);
  return 1 + Math.max(leftHeight, rightHeight); // 1 for this node
}

// Build the sample tree
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);

console.log("Height of the tree:", height(root));

Height of the tree: 3

⏱️ How Fast Is It?

Let us think about the cost. The function visits each node exactly once. At each node it does a tiny bit of work. Just one comparison and one addition. So the time grows in line with the number of nodes.

There is also the space cost. Recursion uses the call stack, which is the memory the program keeps for function calls that have not finished yet. The deepest the stack ever gets equals the height of the tree.

Here is the full picture side by side.

A skewed tree is one where every node has only one child, so it looks like a long chain. In that case the height equals the number of nodes, and the stack gets that deep too.

⚠️ Common Mistakes to Watch For

A few slips trip up almost everyone the first time. Keep these in mind.

• Forgetting the base case. If you never return 0 for an empty node, the function calls itself forever and crashes.
• Mixing the two counting rules. Pick nodes or edges, then keep the same rule across the whole problem. Do not start with nodes and switch to edges midway.
• Adding the children heights instead of taking the larger one. You want the longer path, so you take the max, not the sum.
• Adding 1 in the wrong place. The 1 is for the current node, so it goes outside the max, not inside.

🧩 What You’ve Learned

• ✅ The height of a tree is the longest path from the root down to a leaf, and you can count it in nodes or in edges.
• ✅ The recursive rule is short: a node’s height is 1 plus the larger of its two children’s heights.
• ✅ The base case is an empty node, which returns 0 when you count nodes.
• ✅ You took the larger child height, not the sum, because you want the longest path.
• ✅ The method runs in O(n) time because it visits every node exactly once.

🚀 What’s Next?

• Tree Traversals
• Maximum Depth of Binary Tree