222. Count Complete Tree Nodes

At a Glance

• Topic: trees
• Pattern: Binary search on tree using heights along left/right spines
• Difficulty: Easy
• Companies: Amazon, Google, Bloomberg, Meta, Microsoft
• Frequency: Medium
• LeetCode: 222

Problem (one-liner)

Given the root of a complete binary tree, return the number of nodes. Complete means every level is full except possibly the last, which is filled left to right.

Recognition Cues

• Complete binary tree → nearly balanced; compare left-edge height vs right-edge height
• If heights match along leftmost and rightmost paths from a node, subtree is a perfect block → 2^height − 1 nodes without counting recursively
• Otherwise recurse on children for less-than-perfect remainder

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — count every node — O(n) time — misses structure exploitation.
• Better / optimal for definition — O(log² n) time — compute depths down left vs right from each recursive root to decide perfect subtree shortcut.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftEdge := 0
	for node := root; node != nil; node = node.Left {
		leftEdge++
	}
	rightEdge := 0
	for node := root; node != nil; node = node.Right {
		rightEdge++
	}
	if leftEdge == rightEdge {
		return (1 << leftEdge) - 1
	}
	return 1 + countNodes(root.Left) + countNodes(root.Right)
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function countNodes(root) {
	if (root === null) {
		return 0;
	}
	let leftEdge = 0;
	for (let node = root; node !== null; node = node.left) {
		leftEdge++;
	}
	let rightEdge = 0;
	for (let node = root; node !== null; node = node.right) {
		rightEdge++;
	}
	if (leftEdge === rightEdge) {
		return (1 << leftEdge) - 1;
	}
	return 1 + countNodes(root.left) + countNodes(root.right);
}

Walkthrough

If subtree rooted at node has left-depth equal right-depth h, it is a perfect binary tree with 2^h − 1 nodes.

Invariant: complete tree property guarantees one branch will eventually hit the perfect shortcut while the other drills down only along the “missing last level” boundary.

Edge Cases

• null → 0
• Single node → left & right depth both 1 → 1 node formula gives 1

Pitfalls

• Using wrong exponent (height vs levels): formula matches depth measured along edges/nodes consistently—here loop counts nodes along spine; (1<<leftEdge)-1 matches standard LeetCode depth convention when left/right walks count levels including root level.

Actually verify: For single node, leftEdge=1, rightEdge=1, (1<<1)-1=1. Good.

For height 3 perfect tree (7 nodes): leftEdge from root going left 3 times? node, node.Left, node.Left.Left - that's 3 levels. (1<<3)-1=7. Good.

Similar Problems

• 104. Maximum Depth of Binary Tree — depth along one path only.
• 110. Balanced Binary Tree — also compares subtree heights.
• 098. Validate Binary Search Tree — unrelated ordering, but rehearses tree metrics.

Variants

• Only count leaves in a complete tree.
• n known in advance—verify with structure without visiting all nodes.

Mind-Map Tags

#trees #complete-binary-tree #binary-search #height-trick #perfect-subtree