EasyTreeDepth-First SearchBinary Tree

Diameter of Binary Tree

1 approach, code in every language

You are given the root of a binary tree. The diameter is defined as the length of the longest path between any two nodes in the tree, measured by the number of edges on that path.

The path does not need to run through the root, and the two endpoints can be any pair of nodes. Return the diameter of the tree.

Example 1

Input: root = [1,2,3,4,5]

Output: 3

The longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), which contains 3 edges.

Example 2

Input: root = [1,2]

Output: 1

The only path connecting two nodes is 1 -> 2, a single edge.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
-100 <= Node.val <= 100

Height-Returning DFS with Global Best

Compute each subtree's height in a single post-order pass and update a running best diameter at every node.

Loading animation…

Intuition

The longest path that bends at a given node uses the tallest path going down its left child plus the tallest path going down its right child. If we know the height of the left subtree and the height of the right subtree, the candidate diameter through that node is simply leftHeight + rightHeight edges. So instead of recomputing heights repeatedly, we let the recursion return the height of each subtree while it bubbles back up. At each node we combine the two child heights to update a global best, then return 1 + max(leftHeight, rightHeight) so the parent can continue the accumulation. Because every node is visited once and does O(1) work, the whole computation is linear.

Algorithm walkthrough

1Keep a shared variable best, initialized to 0, that will hold the largest diameter seen so far.
2Define a helper height(node) that returns the number of edges on the longest downward path from node.
3For a null node return 0; otherwise recurse to get leftHeight and rightHeight.
4Update best = max(best, leftHeight + rightHeight), since a path can bend at this node.
5Return 1 + max(leftHeight, rightHeight) so the parent gets this subtree's height.
6After the traversal finishes, best holds the diameter in edges.

Implementation

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def height(node):
            if not node:
                return 0
            left = height(node.left)
            right = height(node.right)
            self.best = max(self.best, left + right)
            return 1 + max(left, right)

        height(root)
        return self.best

Time

O(n)

Space

O(h)

n is the number of nodes and h is the tree height (recursion stack); h is O(n) in the worst case and O(log n) when balanced.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Widest Gallery Walk is our own problem on the technique behind Diameter of Binary Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free