Count Nodes in Complete Binary Tree - Google Top Interview Questions

                        Solution in C++ :

int solve(Tree* tree) {
    int right_h = 0, left_h = 0;
    auto* curr = tree;
    while (curr) right_h++, curr = curr->right;
    curr = tree;
    while (curr) left_h++, curr = curr->left;
    if (right_h ==
        left_h) {  // if left_height and right_height is same, then the tree has (2**h - 1) nodes
        return (1 << right_h) - 1;
    }
    // If not same, then again make a recursive call on the left and right subtree
    return solve(tree->left) + solve(tree->right) + 1;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public int solve(Tree tree) {
        int lo = 1;
        int hi = 100000;
        while (lo < hi) {
            int m = (lo + hi + 1) / 2;
            boolean exists = check(tree, m);
            if (exists)
                lo = m;
            else
                hi = m - 1;
        }
        return lo;
    }

    public boolean check(Tree t, int m) {
        boolean active = false;
        for (int i = 17; i >= 0; i--) {
            int cur = m & (1 << i);
            if (!active) {
                if (cur > 0)
                    active = true;
            } else {
                if (cur == 0)
                    t = t.left;
                else
                    t = t.right;
                if (t == null)
                    return false;
            }
        }
        return true;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, tree):

        # function to find the left most depth or  the right most depth
        def extreme(root, left):
            height = 1
            if left:
                while root:
                    root = root.left
                    height += 1
            else:
                while root:
                    root = root.right
                    height += 1
            return height

        # main function to solve the problem

        def traverse(root):
            if not root:
                return 0
            l = extreme(root.left, True)
            r = extreme(root.right, False)
            if l == r:  # encountered a full binary tree
                return 2 ** l - 1
            else:
                return traverse(root.left) + traverse(root.right) + 1

        ans = traverse(tree)
        return ans