Diameter of Binary Tree: Global Variables in Binary Tree Traversal

Example problem for this lesson: Diameter of Binary Tree

LeetCode 543 - Diameter of Binary Tree (Easy)

Given a binary tree, compute its diameter. The diameter of a binary tree is the maximum length of a path between any two nodes. This path may or may not pass through the root.

The diameter of a binary tree is a very classic interview question. I’ve encountered it as an original problem in interviews, and I’ve heard friends mention it several times after their own interviews. At the same time, it’s a very representative problem that helps us understand a class of binary tree traversals involving global variables. In this article, I’ll explain the reasoning behind this problem in detail.

This article will cover:

Solving the binary tree diameter problem with subproblems
Solving the binary tree diameter problem with a global variable
Patterns in a class of global variable problems
Related problems

Approach to the Binary Tree Diameter Problem

In Lesson 2, we discussed subproblem decomposition for binary trees (click here to review Lesson 2). The key technique for binary tree problems is to first determine whether the problem can be decomposed into subproblems, and what those subproblems should look like. For the binary tree diameter (longest path) problem, one important thing to note is that the longest path in a binary tree does not necessarily pass through the root:

The longest path in a binary tree does not necessarily pass through the root

This adds some difficulty to our subproblem decomposition. But with a bit of thought, we can still identify the subproblems:

\text{Longest path in the tree} = \max \begin{cases} \text{Longest path in the left subtree} \\ \text{Longest path in the right subtree} \\ \text{Longest path through the root} \end{cases}

Subproblems: longest paths in left and right subtrees

The longest path in the left subtree and the longest path in the right subtree are two subproblems that can be solved recursively. So how do we compute the longest path through the root? It’s the depth of the left subtree plus the depth of the right subtree.

Computing the longest path from the depths of the left and right subtrees

Substituting into the formula above, we get:

\text{Longest path in the tree} = \max \begin{cases} \text{Longest path in the left subtree} \\ \text{Longest path in the right subtree} \\ \text{Depth of the left subtree} + \text{Depth of the right subtree} \end{cases}

Wait a moment. It seems we now have two subproblems: the maximum diameter of a subtree and the maximum depth of a subtree. Does that mean we need to traverse the tree twice? Not at all — we just need to have our traversal function return two values.

Language Tips: How do you return multiple values from a function in different languages?

In C++, use std::pair for two values or std::tuple for more.
// Function return
pair<char, int> foo() {
	return make_pair('a', 314);    
}
// Function call
auto pair = foo();
char a = pair.first;
int b = pair.second;
In Java, use an array if the return values have the same type. If they have different types, you need to write a class yourself.
// Function return
int[] foo() {
    return new int[]{314, 315};
}
// Function call
int[] res = foo();
int a = res[0];
int b = res[1];
In Python, with the tuple type and auto-unpacking, returning multiple values from a function is very natural.
# Function return
def foo():
    return ('a', 314)
# Function call
a, b = foo()

Let’s use Python, which makes returning multiple values convenient, for our example code. We’ll have the traversal function return a 2-tuple: the first value is the maximum depth of the subtree, and the second is the longest path (diameter) in the subtree.

# return (depth, diameter)
def traverse(root):
    if root is None:
        return (0, 0)

    left_depth, left_diam = traverse(root.left)
    right_depth, right_diam = traverse(root.right)
    # Standard method for computing binary tree depth
    depth = 1 + max(left_depth, right_depth)
    # Apply the longest path formula we derived above
    diam = max(left_diam, right_diam, left_depth + right_depth)
    return depth, diam

def diameterOfBinaryTree(root):
    depth, diam = traverse(root)
    return diam

Writing this in Python is convenient enough. But what about C++ and Java? It’s painfully cumbersome. Next, let’s see if there’s a better approach for this problem.

Global Variables in Binary Tree Traversal

At first glance, our traversal function must return two values. If we split a two-return-value function into two separate functions, we’d end up with redundant recursion that slows down the algorithm. But if we look at the code more carefully, something stands out:

If we look at the second return value — the subtree’s diameter (longest path) — we notice that all we’re doing is recursively computing the longest path in the left and right subtrees, then using those to compute the longest path for the current tree. Since we’re always looking for the maximum, why not just keep track of the maximum in a global variable?

Amazing! In other words, putting the maximum diameter in the function’s return value means passing a maximum value up level by level all the way back to the starting point of the DFS. With a global variable, the maximum can reach its destination directly.

This way, our function only needs to return a single value. Here’s the solution in Java:

int diameter;

public int diameterOfBinaryTree(TreeNode root) {
    diameter = 0;
    traverse(root);
    return diameter;
}

// Returns the depth of the tree
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = traverse(root.left); // Depth of left subtree
    int right = traverse(root.right); // Depth of right subtree
    // Directly access the global variable
    diameter = Math.max(diameter, left + right);
    return 1 + Math.max(left, right);
}

More Applications of the Global Variable Approach

So, can this global variable approach for binary tree traversal be used to compute things other than maximums? The answer is yes. Here are two more problems as examples.

Applying the Global Variable Approach Beyond max

LeetCode 110 - Balanced Binary Tree (Easy)

Given a binary tree, determine whether it is height-balanced.

In a balanced binary tree, the heights of the left and right subtrees of any node differ by at most 1.

In this problem, “whether the tree is balanced” can be defined as a global variable, initialized to true. When we visit a node, if we find that its left and right subtrees have unbalanced heights, we set the global variable to false.

boolean balanced;

public boolean isBalanced(TreeNode root) {
    balanced = true;
    traverse(root);
    return balanced;
}

// Returns the height of the tree
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = traverse(root.left);
    int right = traverse(root.right);
    // Check whether the current subtree is balanced; update the global variable
    if (Math.abs(left - right) > 1) {
        balanced = false;
    }
    return 1 + Math.max(left, right);
}

LeetCode 563 - Binary Tree Tilt (Easy)

Given a binary tree, compute the tilt of the entire tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. The tilt of a null node is 0. The tilt of the entire tree is the sum of all nodes’ tilts.

In this problem, the tilt of the entire tree can be defined as a global variable. When we visit a subtree, we accumulate its tilt into the global variable.

int tilt;

public int findTilt(TreeNode root) {
    tilt = 0;
    traverse(root);
    return tilt;
}

// Returns the sum of node values
int traverse(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = traverse(root.left);
    int right = traverse(root.right);
    // Compute the tilt of the current subtree; accumulate into the global variable
    tilt += Math.abs(left - right);
    return root.val + left + right;
}

The Principle Behind the Global Variable Approach: Online Algorithms

Let’s observe the values computed by the global variable in our three example problems:

In the binary tree diameter problem, the global variable computes the maximum (max);
In the binary tree tilt problem, the global variable computes the sum (sum);
In the balanced binary tree problem, the global variable computes all, i.e., x1 && x2 && ... && xn.

The key insight is that these max, sum, and all operations aren’t computed all at once. Instead, during the binary tree traversal, each time a value appears, it’s combined with the global variable. When the traversal ends, the global variable holds the final result. There’s a technical term for this kind of computation: online algorithm.

In simple terms, an online algorithm processes input data as a “stream,” handling one element (or a small batch) at a time, without needing to store all the data. The max, sum, and all operations above are all online algorithms. Many other operations are not online algorithms — they’re called offline algorithms. A typical example is standard deviation (stddev).

For binary tree traversal using a global variable, each value is produced one at a time and combined with the global variable; these values are not all stored. Therefore, the operation that the global variable performs should be an online algorithm. Fortunately, max, sum, all, and similar operations are all online algorithms.

Summary

This article explained the technique of using global variables in binary tree traversal. One important thing to note: global variables are just a technique for making code more concise. In fact, not using global variables at all — as we showed at the beginning of this article, having the recursive function return two values — is perfectly viable. When thinking through a binary tree problem, you should first use the standard subproblem analysis to identify the subproblems in the binary tree traversal, and then look for opportunities to optimize with global variables.

More related problems that use global variables in binary tree traversal:

LeetCode 129 - Sum Root to Leaf Numbers (Medium)
LeetCode 1372 - Longest ZigZag Path in a Binary Tree (Medium)
LeetCode 1373 - Maximum Sum BST in Binary Tree (Hard)