The height of a binary tree is defined as the maximum depth from the root to any leaf node. The most efficient way to calculate it is through recursion.
int height(Node* n) {
if (n == NULL) return 0; // base case
int l = height(n->left);
int r = height(n->right);
return 1 + max(l, r); // 1 + max height of left or right subtree
}
Try solving this problem to practice. You can also challenge yourself with this slightly more complex variation.
This concept is applied in the LeetCode problem: Binary Tree Maximum Path Sum.
Core intuition: For each node, we compute two values:
→ The maximum path sum starting from this node and going down one side (either left or right). This value is passed up to the parent to help it calculate its own contribution.
→ The maximum path sum that passes through this node as a "peak" — that is, it includes both left and right paths. This value is used to update the global maximum path sum.
int maxsum(Node* N, int &ans)
{
if(N == nullptr) return 0;
// Recursively get max path sum from left and right
int lh = max(0, maxsum(N->left, ans)); // ignore if negative
int rh = max(0, maxsum(N->right, ans)); // ignore if negative
// Potential max path through current node
int temp = N->val + lh + rh;
ans = max(ans, temp); // update global max
// Return max path sum going upwards (one side only)
return N->val + max(lh, rh);
}