222. Count Complete Tree Nodes

222. Count Complete Tree Nodes (Medium)

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

Note:

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.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

Related Topics:
Binary Search, Tree

Similar Questions:

• Closest Binary Search Tree Value (Easy)

Solution 1.

Given a subtree, we just compute the lengths of the leftmost path and the rightmost path.

• if they are the same, then this subtree is complete and its node count is 2^length - 1.
• otherwise, we recursively count nodes for the left subtree and the right subtree and return the sum of them plus 1.

// OJ: https://leetcode.com/problems/count-complete-tree-nodes/
// Author: github.com/lzl124631x
// Time: O(H^2)
// Space: O(H)
class Solution {
    int countLeft(TreeNode *root) {
        int cnt = 0;
        for (; root; ++cnt, root = root->left);
        return cnt;
    }
    int countRight(TreeNode *root) {
        int cnt = 0;
        for (; root; ++cnt, root = root->right);
        return cnt;
    }
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int left = countLeft(root), right = countRight(root);
        if (left == right) return (1 << left) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

Solution 2.

Minor optimization which prevents us from recomputing the lengths that we've already known.

// OJ: https://leetcode.com/problems/count-complete-tree-nodes/
// Author: github.com/lzl124631x
// Time: O(H^2)
// Space: O(H)
class Solution {
    int countLeft(TreeNode *root) {
        int cnt = 0;
        for (; root; ++cnt, root = root->left);
        return cnt;
    }
    int countRight(TreeNode *root) {
        int cnt = 0;
        for (; root; ++cnt, root = root->right);
        return cnt;
    }
    int count(TreeNode* root, int left = INT_MIN, int right = INT_MIN) {
        if (!root) return 0;
        if (left == INT_MIN) left = countLeft(root);
        if (right == INT_MIN) right = countRight(root);
        if (left == right) return (1 << left) - 1;
        return count(root->left, left - 1, INT_MIN) + 1 + count(root->right, INT_MIN, right - 1);
    }
public:
    int countNodes(TreeNode* root) {
        return count(root);
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/count-complete-tree-nodes/
// Author: github.com/lzl124631x
// Time: O(H^2)
// Space: O(H)
// Ref: https://leetcode.com/problems/count-complete-tree-nodes/discuss/61958/Concise-Java-solutions-O(log(n)2)
class Solution {
    int height(TreeNode *root) {
        return root ? 1 + height(root->left) : -1;
    }
public:
    int countNodes(TreeNode* root) {
        int h = height(root);
        return h < 0 ? 0 : (height(root->right) + 1 == h ? (1 << h) + countNodes(root->right) : (1 << (h - 1)) + countNodes(root->left));
    }
};