DSA sheet · Trees · DFS pattern

Count Complete Tree Nodes

Counting the nodes of a tree is easy: visit each one, which is O(n). The twist here is that LeetCode asks for something faster than O(n). That is only possible because the tree is complete. The teacher first writes the simple O(n) count, then shows how the words "less than linear" point us to logarithmic → levels → height, and how the formula 2^h − 1 lets us count a whole perfect subtree without visiting its nodes. The result runs in O(log² n). This is a great example of using a problem's guarantee to beat the obvious solution.

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 · Complete vs perfect binary trees
• Part A · Brute force: count every node (O(n))
• Part B · Optimal: use the heights (O(log² n))
• Part C · Revision page

Part 0 · Complete vs perfect binary trees

A level is one row of the tree. The height here means the number of levels (a single node has height 1, an empty tree has height 0).

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

        1
      /   \
     2     3
    / \   /
   4   5 6

        1
      /   \
     2     3
    /       \
   4         7

• Perfect tree: every level is completely full.
• Complete tree: every level is full except maybe the last one, and the last level is filled from the left, without gaps.

The teacher describes it from a node's point of view: a node has two children or none, and if it has only one, that child is the left one, never the right one.

        1
       / \
      2   3
     / \
    4   5
   / \
  6   7

Part A · Brute force: count every node

LeetCode 222

1The question in simple words

You get the root of a complete binary tree. Return how many nodes it has. The catch: design an algorithm that runs in less than O(n) time.

        1
      /   \
     2     3
    / \   /
   4   5 6          → answer 6

2What the constraints tell us

• Number of nodes: 0 to 5 × 10⁴ → 0 is allowed, so we need a base case for an empty tree.
• This n is exactly the n in "O(n)". O(n) would be fast enough for 5 × 10⁴ on its own, but the question explicitly asks us to beat it. So the goal is an algorithm whose work grows slower than n.

3Intuition

Before optimising, the teacher writes the most relaxed solution. Each node says: "me (1) + however many are on my left + however many are on my right." Ask that same question at every node, and the root ends up with the total.

4Building the logic

The recursive formula

count(node) = 1 + count(node.left) + count(node.right). The left count comes from a recursive call on root.left, the right count from a call on root.right.

What should None return?

Stand at 4, a leaf. It calls left (None) and right (None) and waits for two numbers, so that it can add 1 for itself. An empty spot has no nodes, so it must return 0. Then 4 gets 0 + 0 + 1 = 1. That's correct: the subtree at 4 has exactly one node.

Why DFS and not BFS for counting?

BFS also works: push the root, pop nodes one by one, push their children, and count the pops. Pops: 1, then 2 and 3, then 4, 5, 6 → 6 pops = 6 nodes. But the queue holds a whole level at a time, which is extra O(n) space that we don't need. So the teacher prefers DFS here.

5Approach steps

1. If root is None → return 0.
2. Count the left subtree recursively.
3. Count the right subtree recursively.
4. Return 1 + left + right.

6Code (Python)

class Solution:
    def countNodes(self, root):
        if root is None:                      # empty spot: 0 nodes
            return 0
        left = self.countNodes(root.left)     # nodes on my left
        right = self.countNodes(root.right)   # nodes on my right
        return 1 + left + right               # plus me

7Code line by line

8Dry run using the call stack

1. count(1) → calls count(2) first. 1 waits for its left answer, and its right call is pending.
2. count(2) → calls count(4).
3. count(4) → left None → 0, right None → 0 → returns 1.
4. Back in count(2): right is count(5) → 0 + 0 + 1 = 1.
5. count(2) = 1 + 1 + 1 = 3 → goes back as 1's left answer.
6. count(3) → left is count(6) = 1, right is None = 0 → returns 1 + 1 + 0 = 2.
7. count(1) = 1 + 3 + 2 = 6 ✓

9Complexity & remember

• Time O(n): every node is visited once. This is not what the question wants.
• Space O(height): the call stack. A complete tree is always balanced, so that's O(log n).

Part B · Optimal: use the heights

1The question in simple words

Same question. Now we really have to do less than O(n) work, which means we can't visit every node.

2What the constraints tell us

• 0 nodes is possible → the None base case stays.
• n = 5 × 10⁴ → log₂ n ≈ 16. An O(log² n) solution does about 16 × 16 ≈ 256 steps, instead of 50,000.
• The word complete in the statement is the real "constraint". The whole trick depends on it.

3Intuition: how the teacher thinks her way to it

1. "Less than linear" → the next smaller usual complexity is logarithmic.
2. In a tree, log n usually means levels. A balanced tree with n nodes has about log n levels.
3. Levels = height. So: can we get the count from the height?
4. Yes, for a perfect tree: a perfect tree of height h has exactly 2^h − 1 nodes. So if a subtree is perfect, we know its count without visiting its nodes, just by measuring its height in O(log n).

4Building the logic from examples

Why 2^h − 1?

Level 0 has 1 node, level 1 has 2, level 2 has 4, level 3 has 8… A perfect tree with h levels has 1 + 2 + 4 + … + 2^h−1 nodes, and that sum is 2^h − 1.

• 3 levels (1, 2, 4): 2³ − 1 = 8 − 1 = 7 ✓
• 4 levels (1, 2, 4, 8): 2⁴ − 1 = 16 − 1 = 15 ✓

But our tree isn't perfect

Our example (1; 2, 3; 4, 5, 6) has 3 levels, but the formula would say 7. It actually has 6, because 3's right child is missing. So first we need a quick way to tell whether a (sub)tree is perfect.

The test: walk the left edge and the right edge

• left height: start at the node and keep going .left only, counting nodes.
• right height: start at the node and keep going .right only, counting nodes.

In a complete tree, the last level fills from the left. So the leftmost path is the deepest and the rightmost path is the shallowest. If they are the same length, the last level reaches all the way to the right → the tree is perfect → return 2^h − 1. If they differ, some nodes on the last level are missing.

When the heights differ: split

If the left and right heights are different, we can't use the formula on this node. So we do what the brute force does, just at this one node: 1 (me) + count(left) + count(right). Each child is again a complete tree, so it gets the same test.

Walking through the example

        1
      /   \
     2     3
    / \   /
   4   5 6

• At 1: left edge 1 → 2 → 4 = 3. Right edge 1 → 3 = 2. Different → split: 1 + count(2) + count(3).
• At 2: left edge 2 → 4 = 2, right edge 2 → 5 = 2. Equal → perfect → 2² − 1 = 3. We never look inside 2's subtree. ✓
• At 3: left edge 3 → 6 = 2, right edge = 1 (3 has no right child). Different → split: 1 + count(6) + count(None).
• At 6: both edges = 1 → 2¹ − 1 = 1. count(None) = 0. So count(3) = 1 + 1 + 0 = 2.
• count(1) = 1 + 3 + 2 = 6 ✓

Why this is fast: the split only follows one path

The broken spot (where nodes are missing) is only on the last level. Upper levels are always full in a complete tree. When we split a node, the missing part is on one side, so the other child is perfect and finishes in one height check. Only one child per level keeps splitting. So we split at most about one node per level, which means about log n times.

Here is a bigger tree. The bold path is the only one that keeps splitting:

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

count(6) = 1 + 1 + 0 = 2 → count(3) = 1 + 2 + 1 = 4 → count(1) = 1 + 7 + 4 = 12 ✓. Node 2's whole subtree (7 nodes) was counted with two short walks.

The 2^h trick in code: left shift

1 << h means "move the bit 1 left h times", which is exactly 2^h. For example, 1 << 3 = 8. So the formula becomes (1 << lh) - 1. (2 ** lh - 1 means the same thing in Python.)

5Approach steps

1. If root is None → return 0.
2. lh = number of nodes on the path that goes only left.
3. rh = number of nodes on the path that goes only right.
4. If lh == rh → perfect → return 2^lh − 1.
5. Else → return 1 + countNodes(left) + countNodes(right).

6Code (Python)

class Solution:
    def countNodes(self, root):
        if root is None:
            return 0
        lh = self.leftHeight(root)
        rh = self.rightHeight(root)
        if lh == rh:                       # perfect subtree
            return (1 << lh) - 1           # 2^h - 1, no need to visit it
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def leftHeight(self, root):            # walk the left edge
        height = 0
        while root:
            height += 1
            root = root.left
        return height

    def rightHeight(self, root):           # walk the right edge
        height = 0
        while root:
            height += 1
            root = root.right              # RIGHT here (see the bug below)
        return height

7Code line by line

8Dry run using the call stack

Tree 1; 2, 3; 4, 5, 6.

1. count(1): lh = 3 (1, 2, 4), rh = 2 (1, 3). 3 ≠ 2 → split. Call count(2) first.
2. count(2): lh = 2, rh = 2 → equal → return (1 << 2) − 1 = 3. No recursion below 2.
3. Back in count(1): call count(3): lh = 2 (3, 6), rh = 1 (just 3) → split. Call count(6).
4. count(6): lh = 1, rh = 1 → (1 << 1) − 1 = 1.
5. count(None) (3's right) → 0. So count(3) = 1 + 1 + 0 = 2.
6. count(1) = 1 + 3 + 2 = 6 ✓

Compare with Part A: there, the stack went down to every leaf (4, 5, 6). Here, 4 and 5 were never visited one by one.

9Complexity & remember

• One height walk costs O(log n), because a complete tree has about log n levels. Left plus right is 2 log n, which is still O(log n).
• We repeat this at most about once per level, along the one path that keeps splitting, and there are about log n levels. The splits are nested (each one happens inside the previous call), so the costs multiply: log n × log n.
• Time O(log² n), which is far smaller than O(n). On LeetCode this version also ran faster.
• Space O(log n): the recursion only goes down one level at a time along that path, so the stack is at most the height.

Part C · Revision page

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

six = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6)))
seven = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
s = Solution()
print(s.countNodes(six))          # 6
print(s.countNodes(seven))        # 7
print(s.countNodes(TreeNode(1)))  # 1
print(s.countNodes(None))         # 0

Based on this video: Count Complete Tree Nodes | DFS