**Difficulty: Medium**

**Frequency: N/A**

Given a **complete** binary tree, count the number of nodes.

__Definition of a complete binary tree from Wikipedia:__

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^{h} nodes inclusive at the last level h.

**My solution:**

**Data structure:**

**Steps:**

**Complexity:**

Runtime:

Space:

**Test cases:**

**Corner cases:**

**Code:**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int countNodes(TreeNode* root) { int cnt = 0, h = height(root); while (root) { if (height(root->right) == h - 1) { cnt += 1 << h; root = root->right; } else { cnt += 1 << h - 1; root = root->left; } h--; } return cnt; } int height(TreeNode* node) { return !node ? -1 : 1 + height(node->left); } };

**Another solution:**

**Data structure:**

**steps:**

**Complexity**:

Runtime:

Space:

**Code**:

**Things to learn:**

Advertisements