---
tags: leetcode
---

# [222. Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/)
---
# My Solution
## Solution 1: Brute Force (DFS, recursion, post order traversal)
### The Key Idea for Solving This Coding Question
### C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int countNodes(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        int leftCnt = countNodes(root->left);
        int rightCnt = countNodes(root->right);
        return leftCnt + rightCnt + 1;
    }
};

### Time Complexity
$O(n)$
$n$ is the total number of nodes in the complete binary tree.
### Space Complexity
$O(H)$
$H$ is the height of the complete binary tree.
## Solution 2: Binary Search
### The Key Idea for Solving This Coding Question
### C++ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int countNodes(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        int depth = findDepth(root);

        // Assume we have a full binary tree, so all the leaves are in 
        // the bottom level.
        // left is the index for the left-most leaf in the bottom level,
        // while right is the index for the right-most leaf in the bottom level.
        int left = 0, right = (1 << (depth - 1)) - 1;
        while (left < right) {
            // We want to use binary search to determine if the node refered by 
            // middle exists in the bottom level.
            int middle = left + (right - left + 1) / 2;
            if (exist(root, depth, middle)) {
                left = middle;
            } else {
                right = middle - 1;
            }
        }
        if (!exist(root, depth, left)) {
            --left;
        }

        return (1 << (depth - 1)) + left;
    }

private:
    int findDepth(TreeNode *root) {
        int depth = 1;
        while (root->left != nullptr) {
            ++depth;
            root = root->left;
        }
        return depth;
    }

    bool exist(TreeNode *root, int depth, int leafIdx) {
        int left = 0, right = (1 << (depth - 1)) - 1;

        // We want to use binary search to find a index (middle) that
        // is greater than or equal to leafIdx.
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (middle < leafIdx) {
                root = root->right;
                left = middle + 1;
            } else {
                root = root->left;
                right = middle;
            }
        }

        return root != nullptr;
    }
};

### Time Complexity
$O(log(logn))$
$n$ is the number of the nodes in the complete binary tree referred by `root`.
### Space Complexity
$O(H)$
$H$ is the height of the complete binary tree referred by `root`.
# Miscellaneous
<!--
# Test Cases

[1,2,3,4,5,6]

[]

[1]

[1,2]

[1,2,3,4,5,6,7]

-->