DEV Community

Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on

Leetcode - 222. Count Complete Tree Nodes

#leetcode

🧠 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);
};
Enter fullscreen mode Exit fullscreen mode

🔁 Step-by-Step with Example Tree

Let’s say this is our tree:

       1
      / \
     2   3
    /
   4
Enter fullscreen mode Exit fullscreen mode
  • 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)
Enter fullscreen mode Exit fullscreen mode

🔹 Step 2: Go to node 2 

countNodes(2)
= 1 + countNodes(4) + countNodes(null)
Enter fullscreen mode Exit fullscreen mode
  • 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**
Enter fullscreen mode Exit fullscreen mode

🔹 Final Step: Back to root 

countNodes(1)
= 1 + 2 (from node 2) + 1 (from node 3)
= 4
Enter fullscreen mode Exit fullscreen mode

✅ 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
Enter fullscreen mode Exit fullscreen mode

⚙️ 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);
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)