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.

Description Solution Video 13:47

543. Diameter of Binary Tree

Easy66.4% acceptance20 companies

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, 10⁴].
-100 <= Node.val <= 100

Asked at 20 companies

Snapdeal Meta Wix Oracle Verkada Nutanix Aurora

Google Amazon Microsoft Bloomberg Visa

+8 more

Walmart Labs Flipkart Palo Alto Networks Tiktok

TCS NVIDIA Apple DoorDash

Topics

13:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

543. Diameter of Binary Tree

Asked at 20 companies

Topics

Similar problems