Skip to main content
Talentd

Diameter of Binary Tree - Solution & Explanation

EasyTreeDepth-First SearchBinary Tree21 min readAsked at: Amazon, Microsoft, Apple +17
Practice this problem

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is 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.

 

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

 

Constraints:

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

Approach Overview

Problem Overview: You are given the root of a binary tree. The task is to compute the tree's diameter, defined as the number of edges on the longest path between any two nodes. The path may or may not pass through the root.

Approach 1: Depth First Search (Postorder Traversal) (Time: O(n), Space: O(h))

This is the optimal approach used in most interview solutions. Traverse the tree using DFS in postorder. For every node, compute the height of its left and right subtrees. The candidate diameter passing through that node is leftHeight + rightHeight. Maintain a global maximum while returning the subtree height as 1 + max(leftHeight, rightHeight). Each node is visited exactly once, so the time complexity is O(n), and recursion stack usage is O(h), where h is the tree height.

This method works because the longest path in a binary tree must pass through some node as the highest point of the path. DFS allows you to compute subtree heights while updating the best diameter in a single traversal. It's simple, efficient, and the expected approach in most coding interviews involving tree traversal.

Approach 2: Dynamic Programming with Memoization (Time: O(n), Space: O(n))

This approach separates height calculation and diameter evaluation using memoization. First compute the height of every node recursively and store results in a hash map or array keyed by node reference. When evaluating the diameter at a node, look up the cached heights of its left and right children instead of recomputing them. This avoids repeated height calculations that would otherwise make the naive solution O(nĀ²).

The algorithm still performs a traversal of all nodes, keeping overall time complexity at O(n). However, the memoization structure stores subtree heights for every node, increasing auxiliary space usage to O(n) in addition to recursion stack space. This pattern resembles classic depth-first search combined with dynamic programming where intermediate subtree results are cached.

Recommended for interviews: The DFS postorder solution is what interviewers typically expect. It computes height and diameter in a single traversal with minimal space. Implementing it correctly shows strong understanding of recursive tree problems. The memoization version demonstrates awareness of avoiding repeated subtree computations, but the single-pass DFS solution is cleaner and more efficient.

Approach 1: Depth First Search

This approach uses a depth-first search (DFS) to calculate the diameter of the binary tree. The key idea is to determine the longest path passing through each node and update the maximum diameter accordingly.

By computing the height of the left and right subtrees at each node, we can obtain the potential diameter passing through that node as the sum of the heights plus one. We will keep track of the global diameter, updating it as necessary.

The implementation involves a helper function dfs that traverses the tree recursively. For each node, it calculates the height of the left and right subtrees. The diameter is updated as the maximum of the current diameter and the sum of the heights of the left and right subtrees. The function diameterOfBinaryTree initializes the diameter and invokes the DFS.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes. Each node is visited once.
Space Complexity: O(H), where H is the height of the tree, representing the call stack size due to recursion.

Try this approach in the editor ā†’

Approach 2: Dynamic Programming with Memoization

This method enhances the recursive DFS approach by incorporating memoization for subtree height calculations, thereby eliminating redundant computations and improving performance, especially beneficial for trees with high duplication of node structures.

Memoization is implemented using an auxiliary array memo, which stores the height of each node index as calculated by DFS to avoid redundant computations. TreeNode indexing assumes a complete binary tree structure for simplicity in accessing child indices.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: Approaches O(N) due to controlled redundant calculations via memoization.
Space Complexity: O(N) for storing the heights in the memo array.

Try this approach in the editor ā†’

Approach 3: Enumeration + DFS

We can enumerate each node of the binary tree, and for each node, calculate the maximum depth of its left and right subtrees, l and r, respectively. The diameter of the node is l + r. The maximum diameter among all nodes is the diameter of the binary tree.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#C

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

C

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Depth First Search

Time Complexity: O(N), where N is the number of nodes. Each node is visited once.
Space Complexity: O(H), where H is the height of the tree, representing the call stack size due to recursion.

Dynamic Programming with Memoization

Time Complexity: Approaches O(N) due to controlled redundant calculations via memoization.
Space Complexity: O(N) for storing the heights in the memo array.

Enumeration + DFSā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth First Search (Postorder)O(n)O(h)Best general solution. Single traversal computes subtree heights and diameter simultaneously.
Dynamic Programming with MemoizationO(n)O(n)Useful when subtree heights are reused across multiple computations or when illustrating DP optimization over repeated recursion.

Video Solution

L16. Diameter of Binary Tree | C++ | Java ā€¢ take U forward ā€¢ 629,509 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Diameter of Binary Tree easy or hard?
Diameter of Binary Tree is categorized as an Easy problem on LeetCode. Despite the label, it tests an important pattern: computing subtree information during DFS while updating a global result, which appears in many tree interview questions.
Diameter of Binary Tree Python/Java solution
In Python or Java, the solution typically defines a recursive DFS function that returns subtree height while updating a global or class-level variable storing the maximum diameter. The logic is identical across languages and runs in O(n) time.
How to solve Diameter of Binary Tree in O(n)?
Use a single DFS traversal that returns the height of each subtree. At every node, compute leftHeight and rightHeight recursively and update a global diameter with leftHeight + rightHeight. Returning 1 + max(leftHeight, rightHeight) allows height and diameter to be calculated in one pass.
What is the best approach for Diameter of Binary Tree?
The best approach uses Depth First Search with postorder traversal. For each node, compute the height of the left and right subtrees and update the diameter as leftHeight + rightHeight. This processes every node once, resulting in O(n) time and O(h) recursion stack space where h is the tree height.
Is Diameter of Binary Tree asked at Google/Amazon/Meta?
Diameter of Binary Tree is a common tree recursion problem frequently asked in technical interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of DFS traversal, recursion, and combining subtree results efficiently.
What data structure is used in Diameter of Binary Tree?
The problem operates on a binary tree data structure and is typically solved using Depth First Search recursion. Some variations also use memoization maps to cache subtree heights when applying dynamic programming techniques.
What is the time complexity of Diameter of Binary Tree?
The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. The recursion stack uses O(h) space where h is the height of the tree, which becomes O(n) in the worst case for a skewed tree.

Ready to solve this problem?

Practice Diameter of Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Diameter of N-Ary Tree

Next

Longest Path With Different Adjacent Characters