1. Understanding the Problem

You are given the root of a binary tree. Your task is to return the length of the diameter of the tree.

The diameter of a binary tree is defined as the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

The Core Constraint (The Trap):

It is incredibly tempting to assume that the longest path must always pass through the main root node of the tree (i.e., height(left) + height(right)). This is a trap! In unbalanced or top-heavy trees, the longest path might be fully contained within a deep sub-tree far down on one side, never touching the root at all.

2. The Naive Approach: Recalculating Heights at Every Node

The most intuitive way to solve this is to write a helper function that calculates the height/depth of a tree. Then, for every single node in the binary tree, you compute the depth of its left subtree and the depth of its right subtree, add them together to find the local diameter, and pick the maximum.

Trade-off Analysis

While this logic is sound and mathematically correct, it is highly redundant:

• Time Complexity: O(N²) — For every node (N), you re-traverse its child nodes to calculate their heights (N). In a skewed tree, this quadratic complexity will trigger a "Time Limit Exceeded" error.
• Space Complexity: O(H) — Where H is the height of the tree, due to the recursive call stack.

3. The Optimal Approach: Bottom-Up Depth-First Search (O(N) Time)

To pass a senior-level technical interview, we want to achieve a linear O(N) time complexity. We can do this by calculating heights and updating the global diameter simultaneously during a single post-order traversal.

Imagine managing a company's reporting structure from the bottom up. Instead of the CEO asking every department head to recalculate their team size from scratch every day, each junior manager calculates their own team size and reports it up to their supervisor. As the information travels upward, the supervisor tracks the longest combined chain among their subordinates while passing their own height up to the next level.

At any given node, the maximum path passing through that node as a turning point is left_height + right_height. The height that the node passes up to its parent is max(left_height, right_height) + 1.

4. The Logic Step-by-Step

1. Initialize a global (or outer class) variable max_diameter = 0 to keep track of the largest diameter found so far.
2. Define a recursive helper function get_height(node):
   • Base Case: If node is null, return 0 (a non-existent node has a height of 0).
   • Recurse Left: Calculate left_height = get_height(node.left).
   • Recurse Right: Calculate right_height = get_height(node.right).
   • Update Global State: The longest path passing through this current node is left_height + right_height. Update max_diameter = max(max_diameter, left_height + right_height).
   • Return Height to Parent: Return the height of the current node to its parent: 1 + max(left_height, right_height).
3. Call get_height(root) to kick off the bottom-up traversal.
4. Return max_diameter.

5. Complexity Analysis

• Time Complexity: O(N) — We visit every node in the binary tree exactly once. Heights are calculated bottom-up without redundant traversals.
• Space Complexity: O(H) — Where H is the height of the tree. In the worst-case scenario (a skewed, line-like tree), the recursion call stack will take O(N) space. For a balanced tree, space complexity is O(log N).

6. Code Implementations

Expand the sections below to see the optimal O(N) "Post-Order DFS" implementations across different languages.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def get_height(node):
            if not node:
                return 0
                
            # Post-order traversal: compute left and right heights bottom-up
            left_height = get_height(node.left)
            right_height = get_height(node.right)
            
            # Update the global diameter if the path through current node is larger
            self.max_diameter = max(self.max_diameter, left_height + right_height)
            
            # Return height of current node to parent
            return 1 + max(left_height, right_height)
            
        get_height(root)
        return self.max_diameter

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        getHeight(root);
        return maxDiameter;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);

        // Update the global diameter tracker
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        // Return height of current subtree
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

#include <algorithm>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int maxDiameter = 0;

    int getHeight(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);

        // Update the global diameter if path through current node is larger
        maxDiameter = std::max(maxDiameter, leftHeight + rightHeight);

        // Return height of current node to parent
        return 1 + std::max(leftHeight, rightHeight);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        getHeight(root);
        return maxDiameter;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered one of the most essential tree recursion patterns! Understanding how to combine return values (subtree heights) with global side-effects (updating the maximum diameter) is a critical milestone in algorithm design. This exact "bottom-up post-order" architecture is used to solve many advanced tree questions, including Balanced Binary Tree, Binary Tree Maximum Path Sum, and Lowest Common Ancestor. Keep this mental model sharp, and you will confidently navigate tree recursion in any technical interview!