Lesson 7 · Advanced structures and algorithms

Tree Diameter and Height

The diameter of a tree is the maximum distance between any two leaves, which often does not pass through the root node.

Height vs Diameter

The height of a tree is the maximum depth from the root to a leaf. The diameter, however, is the longest path between any two nodes in the tree. While related, the diameter path might exist entirely within a single dense subtree and never touch the global root.

The Post-order Formula

We can compute the diameter in O(N) time using post-order traversal. At each node, we recursively find the maximum height of its left and right subtrees. The longest path passing through this specific node is simply the sum of those two heights.

Key reference

Terms, operations, and practical uses

Definitions

Tree DiameterThe length of the longest path between any two nodes in a tree. It does not necessarily pass through the root.
Node HeightThe maximum number of edges on a path from the node down to a leaf.
Path LengthUsually defined by the number of edges between nodes, though sometimes defined by the number of nodes.

Recursive Approach

Post-order AggregationAt each node, compute the height of the left and right subtrees first.
Local Path ComputationThe longest path passing through a specific node is exactly left_height + right_height.
Global StateMaintain a global maximum variable that is updated if the current node's local path exceeds the known maximum diameter.

Graph Approach

First BFSStart a Breadth-First Search from any arbitrary node to find the furthest possible node, which we'll call Node A.
Second BFSStart a second BFS from Node A. The furthest node from A is Node B. The path from A to B is the diameter.
ApplicabilityThis two-BFS method works on any unrooted tree (acyclic graph) and avoids deep recursion stacks.

Code example

Measure the longest path in a tree

class Solution:
    def diameterOfBinaryTree(self, root):
        self.dia = 0
        def height(node):
            if not node: return 0
            l = height(node.left)
            r = height(node.right)
            self.dia = max(self.dia, l + r)
            return 1 + max(l, r)
        height(root)
        return self.dia
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = TreeNode(1, TreeNode(2), TreeNode(3))
print('Diameter:', Solution().diameterOfBinaryTree(root))

class Solution {
    int dia = 0;
    int height(TreeNode* node) {
        if (!node) return 0;
        int l = height(node->left);
        int r = height(node->right);
        dia = max(dia, l + r);
        return 1 + max(l, r);
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return dia;
    }
};

class Solution {
    int dia = 0;
    int height(TreeNode node) {
        if (node == null) return 0;
        int l = height(node.left);
        int r = height(node.right);
        dia = Math.max(dia, l + r);
        return 1 + Math.max(l, r);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return dia;
    }
}

Inputthree-node tree with two leaf children

OutputDiameter: 2

Example

Run the example step by step

Output

Updating the Global Maximum

As we calculate the local left-plus-right path length for every node, we constantly update a global maximum variable. After the traversal finishes, the node returns its own height (1 + max(left, right)) to its parent, while the global variable holds the true diameter.

Two-BFS Method for N-ary Trees

For unrooted graphs or N-ary trees, a different O(N) strategy is used: pick a random node and run BFS to find the farthest node A. Then, run a second BFS starting from A. The farthest node from A is node B, and the distance between them is the tree's diameter.