[O(log(n)^2) C++ Binary Search Method] Concise with explanation

• ``````class Solution {
private:
/// This mask is used to check the highest bit in a int number.
int mask = 1 << 31;

/// *code* is an int number that encodes the path to the leaf.
/// *counter* is the height of the full binary tree (upper n - 1 levels).
bool check (TreeNode* root, int code, int counter) {
code <<= (32 - counter);
while (counter > 0) {
/// When the highest code is 0, move to left. Otherwise move to left.
if (code & mask) root = root->right;
else root = root->left;

code <<= 1;
--counter;
}
return root != nullptr;
}

public:
int countNodes(TreeNode* root) {
int counter = 0;
TreeNode *left = root, *right = root;
while (left && right) {
left = left->left;
right = right->right;
++counter;
}
if (counter == 0) return 0;
if (!left) return (pow(2, counter) - 1);

/// leftcode encodes the path to the left most leaf (all 0s).
/// rightcode encodes the path to the right most (possible) leaf (all 1s).
int leftcode = 0, rightcode = 0;
for (int i = 0; i < counter; ++i) {
rightcode <<= 1;
rightcode += 1;
};

while (leftcode != rightcode && leftcode != rightcode - 1) {
/// Get path to the middle leaf node.
int mid = leftcode + (rightcode - leftcode) / 2;
if (check(root, mid, counter)) leftcode = mid;
else rightcode = mid - 1;
}

if (check(root, rightcode, counter)) return pow(2, counter) + rightcode;
else return pow(2, counter) + leftcode;
}
};
``````

• Yes, this method has limitation - the height of this tree must be smaller than 32 (or we can use long to extend this limitation).

Time complexity of this method is O(log(n) * log(n))

• Need log(n) times to check the leaf node is null or not.
• For each check, we need O(height) = O(log(n)) moves along the tree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.