https://leetcode.com/problems/count-complete-tree-nodes/

Brutal force

If we ignore the fact that the tree is complete, then we just count compute the number of nodes naively:

1
2
3
4
5
6
public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

The complexity is O(n) n is the number of nodes in the tree.

Better one

Since we know the tree is a complete binary tree, only the leaf nodes are not full. Hence, the number of nodes of every level of the tree except the last one is 2^d, d is the depth of the node.

Based on the brutal force method, we could add some code to return the result immediately if the tree with root is a full binary tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int countNodes(TreeNode root) {
        int h = 0;
        TreeNode left = root, right = root;
        while (right != null) {
            left = left.left;
            right = right.right;
            h++;
        }
        if (left == null) { // is a full binary tree, number of node is 2^(heigth + 1) - 1
            return (1 << h) - 1;
        } else {
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }
}

At least one of the two recursive calls will return immediately since at least one of them is a full binary tree. Proof:

  • If left subtree is not full binary tree, the right is full has one less height of left one.
  • If right subtree is not full binary tree, the left must be.

So, since one of the recursive call will return, it is essentially cut in half binary search complexity. And each countNode() has a O(logn) for the depth of the tree. So O((logn)^2)