Leetcode - 222. Count Complete Tree Nodes

🧠 Intuition

When you're at any node:

• Count yourself → that’s 1
• Count everything in your left subtree
• Count everything in your right subtree

So, the total nodes at any point =
👉 1 + countNodes(left) + countNodes(right)

---

📦 Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if (root === null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
};

---

🔁 Step-by-Step with Example Tree

Let’s say this is our tree:

       1
      / \
     2   3
    /
   4

• Node 1 has two children
• Node 2 has one child (node 4)
• Node 3 has no children
• Node 4 has no children

---

👇 Call Stack Walkthrough

🔹 Step 1: Start from root

countNodes(1)
= 1 + countNodes(2) + countNodes(3)

---

🔹 Step 2: Go to node 2

countNodes(2)
= 1 + countNodes(4) + countNodes(null)

• countNodes(4) = 1 (it’s a leaf)
• countNodes(null) = 0

So, countNodes(2) = 1 + 1 + 0 = 2

---

🔹 Step 3: Go to node 3

countNodes(3)
= 1 + countNodes(null) + countNodes(null)
= 1 + 0 + 0 = **1**

---

🔹 Final Step: Back to root

countNodes(1)
= 1 + 2 (from node 2) + 1 (from node 3)
= 4

✅ Total nodes = 4

---

🔍 Visual Call Tree

countNodes(1)
├── countNodes(2)
│   ├── countNodes(4)
│   │   ├── countNodes(null) → 0
│   │   └── countNodes(null) → 0
│   └── countNodes(null) → 0
└── countNodes(3)
    ├── countNodes(null) → 0
    └── countNodes(null) → 0

---

⚙️ Time Complexity

• Each node is visited once
• So total time is O(n), where n is number of nodes

---

🎯 Key Takeaway

This line does everything:

return 1 + countNodes(root.left) + countNodes(root.right);

It says:
✅ “I am 1 node, plus whatever is on my left, plus whatever is on my right.”

---