Trick: How to Count Nodes in a Complete Binary Tree

labuladongOriginalAbout 1447 words

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCode	Difficulty
222. Count Complete Tree Nodes	🟠

Prerequisites

Before reading this article, you should first learn:

If you are asked to count the number of nodes in a regular binary tree, it's straightforward. You just need to add a bit of code to the binary tree traversal framework.

However, LeetCode Problem 222, "Count Complete Tree Nodes," asks you to count the number of nodes in a complete binary tree. Are you able to do it? What is the algorithm's time complexity?

The time complexity of this algorithm should be $O(logN*logN)$ . If your approach is not as efficient, then this article is written for you.

For definitions of terms like "complete binary tree" and "full binary tree," you can refer to the Basics of Binary Trees section.

1. Thought Process Analysis

Now, back to the main topic: how do you count the number of nodes in a complete binary tree?

Trick: How to Count Nodes in a Complete Binary Tree

222. 完全二叉树的节点个数 https://leetcode.cn/problems/count-complete-tree-nodes

222. Count Complete Tree Nodes https://leetcode.com/problems/count-complete-tree-nodes

1. Thought Process Analysis

2. Complexity Analysis