← Back to DSA Course | Chapter 11: Trees | Lesson 7 of 10

Height and Diameter of Tree

Height is how many steps the longest path from the top of the tree to a leaf takes, and diameter is the longest path between any two leaves, like measuring across the widest part of a tree.

In this page:

  1. Tree Height
  2. Recursive Height
  3. Tree Diameter
  4. Height and Diameter Together
  5. Practice
Syntax
markup 
def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

Tree Height

A tree's height is the length of the longest path from the root down to any leaf, typically measured in either number of edges or number of levels depending on the convention chosen — this course counts it in node levels.

Example: Tree Height

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Height in levels: 2 (root -> leaf), or 1 edge from root to leaf" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Height in levels: 2 (root -> leaf), or 1 edge from root to leaf");
    }
}
print("Height in levels: 2 (root -> leaf), or 1 edge from root to leaf")
#include <stdio.h>
int main() {
    printf("Height in levels: 2 (root -> leaf), or 1 edge from root to leaf\n");
    return 0;
}

Recursive Height

Height is computed recursively: a node's height is one plus the larger of its left and right subtree's heights, with an empty subtree contributing a height of zero (or negative one, depending on convention) as the recursive base case.

Example: Recursive Height

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int height(Node* n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Height: " << height(&root) << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int height(Node n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Height: " + height(root));
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Height:", height(root))
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int height(struct Node* n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Height: %d\n", height(&root));
    return 0;
}

Tree Diameter

A tree's diameter is the length of the longest path between any two nodes in the tree, which may or may not pass through the root — this makes diameter trickier than height, since the longest path could be entirely within one subtree.

Example: Tree Diameter

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int height(Node* n) { if(!n) return 0; int l=height(n->left), r=height(n->right); return 1+(l>r?l:r); }
int diameter(Node* n) {
    if (!n) return 0;
    int through = height(n->left) + height(n->right);
    int left = diameter(n->left), right = diameter(n->right);
    int best = through > left ? through : left;
    return best > right ? best : right;
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "Diameter: " << diameter(&root) << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int height(Node n) { if(n==null) return 0; return 1+Math.max(height(n.left),height(n.right)); }
    static int diameter(Node n) {
        if (n == null) return 0;
        int through = height(n.left) + height(n.right);
        return Math.max(through, Math.max(diameter(n.left), diameter(n.right)));
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Diameter: " + diameter(root));
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def height(n):
    if n is None: return 0
    return 1 + max(height(n.left), height(n.right))

def diameter(n):
    if n is None:
        return 0
    through = height(n.left) + height(n.right)
    return max(through, diameter(n.left), diameter(n.right))

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("Diameter:", diameter(root))
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int height(struct Node* n) { if(!n) return 0; int l=height(n->left), r=height(n->right); return 1+(l>r?l:r); }
int diameter(struct Node* n) {
    if (!n) return 0;
    int through = height(n->left) + height(n->right);
    int left = diameter(n->left), right = diameter(n->right);
    int best = through > left ? through : left;
    return best > right ? best : right;
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("Diameter: %d\n", diameter(&root));
    return 0;
}

Height and Diameter Together

Diameter and height can be computed together in a single traversal: while computing each node's height recursively, also check whether the path through that node (left height plus right height) beats the best diameter seen so far.

Example: Height and Diameter Together

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int best = 0;
int heightAndDiameter(Node* n) {
    if (!n) return 0;
    int l = heightAndDiameter(n->left), r = heightAndDiameter(n->right);
    if (l + r > best) best = l + r;
    return 1 + (l > r ? l : r);
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    int h = heightAndDiameter(&root);
    cout << "Height: " << h << ", Diameter (computed in same pass): " << best << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static int best = 0;
    static int heightAndDiameter(Node n) {
        if (n == null) return 0;
        int l = heightAndDiameter(n.left), r = heightAndDiameter(n.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        int h = heightAndDiameter(root);
        System.out.println("Height: " + h + ", Diameter (computed in same pass): " + best);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

best = 0
def height_and_diameter(n):
    global best
    if n is None:
        return 0
    l = height_and_diameter(n.left)
    r = height_and_diameter(n.right)
    best = max(best, l + r)
    return 1 + max(l, r)

root = Node(5)
root.left = Node(3); root.right = Node(8)
h = height_and_diameter(root)
print("Height:", h, ", Diameter (computed in same pass):", best)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int best = 0;
int heightAndDiameter(struct Node* n) {
    if (!n) return 0;
    int l = heightAndDiameter(n->left), r = heightAndDiameter(n->right);
    if (l + r > best) best = l + r;
    return 1 + (l > r ? l : r);
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    int h = heightAndDiameter(&root);
    printf("Height: %d, Diameter (computed in same pass): %d\n", h, best);
    return 0;
}

Practice

Height and diameter problems are a common category of tree recursion exercise because they require combining a straightforward recursive computation (height) with tracking a running best value (diameter) across the whole traversal.

Example: Practice

#include <iostream>
using namespace std;
int main() {
    cout << "Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step");
    }
}
print("Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step")
#include <stdio.h>
int main() {
    printf("Height/diameter combine a straightforward recursion with an extra 'track the best answer seen' step\n");
    return 0;
}
Related Topics

AVL Tree · Tree Views Left Right Top Bottom · Binary Search Tree · Serialize and Deserialize Tree

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Mixing up counting nodes and counting edges, so a single node is height 1 in one place and 0 in another.
  2. Forgetting that the diameter may not pass through the root, so only height(left) + height(right) at the root is checked.
  3. Recomputing height at every node inside the diameter loop, which makes it O(n^2).
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson AVL Tree Next Lesson → Lowest Common Ancestor

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.