Height of a tree

The number of nodes on the longest path from the root down to a leaf, computed bottom-up.

Time O(n)Space O(h)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A node cannot know its height until both children report theirs. Its own height is one more than the taller child. An empty subtree has height 0.

Code

C++PythonC#

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

def max_depth(node: TreeNode | None) -> int:
    if node is None: return 0
    left = max_depth(node.left)
    right = max_depth(node.right)
    return 1 + max(left, right)

public static int MaxDepth(TreeNode node) {
    if (node == null) return 0;
    int left = MaxDepth(node.left);
    int right = MaxDepth(node.right);
    return 1 + Math.Max(left, right);
}

Tips

This "ask the children, combine, return" shape solves most tree problems: diameter, balanced check, path sums.

In the .NET library

Very deep trees can overflow the call stack (StackOverflowException cannot be caught). For untrusted depth, use an explicit Stack<T> or the level order loop.