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


  • 0
    H
    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;
        }
    };
    

  • 0
    H

    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.

Log in to reply
 

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