DSA sheet · Trees · DFS pattern

Diameter of Binary Tree

The teacher calls this a very common question for freshers. She solves it twice: first with BFS, which is easy to think of but slow (O(n²)), and then with DFS, which does the same job in one pass, O(n). The big lesson is one DFS can do two jobs at once: return a height to the parent, and quietly update the best answer on the side. This trick comes back again in Balanced Binary Tree and Maximum Path Sum, so learn it well here.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Words you must know first
• Part A · Diameter with BFS (brute force, O(n²))
• Part B · Diameter with DFS (optimal, O(n))
• Part C · Revision page

Part 0 · Words you must know first

Part A · Diameter with BFS (brute force)

LeetCode 543

1The question in simple words

You get the root of a binary tree. Return its diameter: the length (number of edges) of the longest path between any two nodes. The path does not have to go through the root.

This is the tree the teacher uses for the whole video:

              1
            /   \
           2     3
         /   \
        4     5
       /     / \
      9     6   7
       \       /
        10    8

Let's stand on each node and ask: "If the path bends at me, how far can it go down on my left, and how far on my right?" Add the two, and you get the longest path that bends at this node.

The biggest value is at node 2: the path 10 – 9 – 4 – 2 – 5 – 7 – 8. It touches 7 nodes but has 6 edges, so the answer is 6.

2What the constraints tell us

• Number of nodes: 1 to 10⁴ → there is always at least one node. In BFS the loop simply ends when the queue is empty, so a top-level empty check isn't strictly needed (the teacher still adds one as a safety guard). In DFS we always need a base case, because recursion keeps diving into children and needs something to stop it.
• n can be 10⁴ → an O(n²) solution means about 10⁸ steps. That is right at the edge: it will pass, but slowly. If n were 10⁵, n² = 10¹⁰ and it would surely give TLE.
• Node values: −100 to 100. The teacher explains why we read value limits at all: if we add or multiply values, a big total (beyond about 10⁹) wouldn't fit in a normal int in Java/C++ and would need long. Here we only count edges and never add the values, so the values don't matter. (In Python ints never overflow anyway.)

3Intuition: how to think about it

From the table above, the plan is clear: for every node, find the height of its left subtree and the height of its right subtree, add them, and keep the biggest sum.

The BFS way to do that: walk through all nodes level by level using a queue. For each node we take out, ask a helper "how tall is my left subtree? how tall is my right subtree?" The helper itself does a level-order traversal and simply counts the levels.

4Building the logic from examples

Why "levels" of a subtree = "edges" on that side

Take node 1. Its left subtree starts at 2 and has 4 levels: (2), (4, 5), (9, 6, 7), (10, 8). The longest way down on 1's left is 1→2→4→9→10, which is 4 edges. The same number!

Why? If you count only the edges inside the subtree (2→4→9→10) you get 3. But the path from 1 also uses the edge 1→2. Counting levels (nodes) of the subtree instead of edges inside it adds exactly that one missing edge. So:

Check for node 1: left height 4 + right height 1 (just node 3) = 5, matching the table.

The outer BFS: visit every node

• Put the root in a queue. Start diameter = 0.
• Pop a node. Call height(node.left) and height(node.right).
• Update diameter = max(diameter, left + right). For node 1 this changes 0 → 5.
• Push its children (2 and 3) so they get their turn.

The helper height(): level order, but just count

This is the level-order traversal from the earlier video, with one change. There we stored every level in its own sub-list, and the number of sub-lists was the height. That wastes space. Here we don't store anything: we just add 1 to a counter each time a full level is finished.

A small practice tree the teacher uses:

      2
     / \
    3   4
       / \
      5   6

• Queue = [2]. Size 1 → pop 2, push 3, 4. Level done → height = 1.
• Queue = [3, 4]. Size 2 → pop 3 (no children), pop 4 (push 5, 6). Level done → height = 2.
• Queue = [5, 6]. Size 2 → pop both, nothing to push. Level done → height = 3.
• Queue empty → return 3.

5Approach steps

1. If the tree is empty, return 0. Set diameter = 0 and put the root in a queue.
2. While the queue is not empty, pop a node.
3. Find left = height(node.left) and right = height(node.right) with a level-order count.
4. Set diameter = max(diameter, left + right).
5. Push the node's children that exist.
6. When the queue is empty, return diameter.

6Code (Python)

from collections import deque

class Solution:
    def diameterOfBinaryTree(self, root):
        if root is None:                       # safety guard
            return 0
        diameter = 0
        queue = deque([root])
        while queue:
            node = queue.popleft()
            left = self.height(node.left)      # levels on the left
            right = self.height(node.right)    # levels on the right
            diameter = max(diameter, left + right)
            if node.left:                      # push only real children
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return diameter

    def height(self, root):                    # level order, only counting
        if root is None:
            return 0
        queue = deque([root])
        height = 0
        while queue:
            size = len(queue)                  # nodes on this level
            for _ in range(size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            height += 1                        # one full level finished
        return height

7Code line by line

8Dry run: watch the outer queue

On the main tree. Each line pops one node and calls the helper twice.

Notice how the helper re-walks the same nodes again and again: node 10 is counted when we pop 1, again when we pop 2, again for 4, and again for 9. That repeated work is what makes this slow.

9Complexity & remember

• Time O(n²): the outer loop visits n nodes. For each one, the helper walks its left part (about n/2 nodes) and right part (about n/2), so up to about n work per node. n × n = n². With n = 10⁴ that's 10⁸, so the code is accepted but slow. (For a perfectly balanced tree it's really closer to n log n; the n² worst case shows up for long, line-shaped trees. In an interview, call it O(n²).)
• Space O(2n) → O(n): one queue for the outer BFS, plus a second queue inside the helper.

Part B · Diameter with DFS (optimal)

1The question (same as Part A)

Same tree, same answer (6). The meaning of diameter doesn't change. Only the way we collect the heights changes.

2What the constraints tell us

• n up to 10⁴: an O(n) solution is about 10⁴ steps, very fast.
• DFS is recursion, so a base case is a must (the None child). Without it the calls never stop.

3Intuition: the answer comes from below

Standing on node 1, can we decide anything about its diameter? No. We need the heights from below first. So we shouldn't do work at the node and then go down (like preorder). We should go down first, collect the answers from the children, and only then decide at the node. That's postorder thinking: left, right, then the node.

And here is the saving: when a child finishes, it already knows its own height. It just hands that number up. The parent never has to re-walk the subtree like the BFS helper did. Each node is visited once.

4Building the logic from examples

Base case: what does an empty child return?

The parent wants to add the left answer and the right answer. If an empty child returned None, how would node 3 add None + None? It can't. So an empty spot returns 0: "no levels here".

At a node: update the diameter

Look at leaf 10: left gives 0, right gives 0. Forget the rest of the tree. Just this one node has no edges, so its diameter is 0 + 0 = 0. In general, once we have left and right:

What should the node return to its parent? Not the diameter!

Try returning the diameter. Leaf 10 would return 0 to node 9. But for 9, the right side really has 1 edge (9→10). With 0, node 9 would think its diameter is 0, which is wrong. So the return value must be something else.

Now look at node 2 from its parent 1's point of view. Below 2 there are many paths: one through 4 (to 10) and two through 5 (to 6, and to 8). But node 1 can extend only one of them, because a path can't split into two branches. So 2 should hand up the longest single branch.

• Node 5 has a branch of length 1 (to 6) and a branch of length 2 (to 8). It passes up the longer one.
• Then add 1 for node 5 itself (one more level, which becomes the edge to its parent).

So one function does two jobs: it returns the height (needed by the parent) and it updates the diameter in a variable outside the function (needed for the final answer). The value returned by the very first call isn't the answer, so we ignore it and return the diameter variable.

5Approach steps

1. Set diameter = 0 outside the helper. Call height(root), then return diameter.
2. In height(node): if the node is None, return 0.
3. Get left = height(node.left) and right = height(node.right).
4. Update diameter = max(diameter, left + right).
5. Return max(left, right) + 1.

6Code (Python)

class Solution:
    def diameterOfBinaryTree(self, root):
        self.diameter = 0                # best path length seen so far
        self.height(root)                # fills self.diameter
        return self.diameter

    def height(self, root):
        if root is None:                 # base case: no levels
            return 0
        left = self.height(root.left)    # height of left subtree
        right = self.height(root.right)  # height of right subtree
        self.diameter = max(self.diameter, left + right)   # job 1
        return max(left, right) + 1                         # job 2

In Java the teacher keeps diameter as a class field. In Python we use self.diameter and reset it at the top of the main method, so calling the method twice on the same object can't mix answers.

7Code line by line

8Dry run using the call stack

Main tree again. Each line shows (left, right) → what's written on the board → what's returned.

1. Calls go down the left edge: h(1) → h(2) → h(4) → h(9) → h(9.left = None) returns 0.
2. h(9) goes right: h(10). Both its children are None → left 0, right 0. Board: max(0, 0) = 0. Returns max(0,0)+1 = 1.
3. Back in h(9): left 0, right 1. Board: max(0, 1) = 1. Returns 1 + 1 = 2.
4. h(4): left 2 (from 9), right 0 (None). Board: max(1, 2) = 2. Returns 2 + 1 = 3.
5. h(2) now goes right: h(5) → h(6): leaf → board stays 2, returns 1.
6. h(5) goes right: h(7) → h(8): leaf → returns 1. h(7): left 1, right 0 → board stays 2 (1 < 2). Returns 2.
7. h(5): left 1, right 2 → board: max(2, 3) = 3. Returns 2 + 1 = 3.
8. h(2): left 3, right 3 → board: max(3, 6) = 6. Returns 3 + 1 = 4 (only one branch goes up).
9. h(1) goes right: h(3): leaf → board stays 6, returns 1.
10. h(1): left 4, right 1 → 5, board stays 6. Returns 5, which nobody needs. Final answer: diameter = 6 ✓

The newest call is on top (red). Each call leaves the stack the moment it returns its height.

9Complexity & remember

• Time O(n): every node is visited exactly once, and each visit does constant work.
• Space O(n): the call stack. It's as tall as the tree: about log n for a balanced tree, n for a line-shaped (skewed) tree.
• On LeetCode the DFS version runs much faster than BFS. For this problem, DFS wins the race.

Part C · Revision page

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

t = TreeNode(1,
        TreeNode(2,
            TreeNode(4, TreeNode(9, None, TreeNode(10))),
            TreeNode(5, TreeNode(6), TreeNode(7, TreeNode(8)))),
        TreeNode(3))
s = Solution()
print(s.diameterOfBinaryTree(t))                                   # 6
print(s.diameterOfBinaryTree(TreeNode(1)))                         # 0
print(s.diameterOfBinaryTree(TreeNode(1, TreeNode(2))))            # 1
print(s.diameterOfBinaryTree(TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))))  # 3

Based on this video: Diameter of Binary Tree | BFS & DFS