Count Complete Tree Nodes

LeetCode Q 222 - Count Complete Tree Nodes

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 2h nodes inclusive at the last level h.

Solution

Method 1

Code:

public int countNodes(TreeNode root) {
	if (root == null) return 0;
	return 1 + countNodes(root.left) + countNodes(root.right);
}

The time complexity of this method O(n). We can do it better as follows.

Method 2

First, use divide and conquer to find the number of nodes.
We use height(root) == height(root.right) - 1 to check if the child is a complete tree.

• If it is, then we can let root = root.rightand find the number of nodes in the right child.
• If it isn’t, then we can let root = root.left and find the number of nodes in the left child.

Code:

public int countNodes(TreeNode root) {
	//return countNodesRecursive(root);
	return countNodesIterative(root);
}

public int countNodesRecursive(TreeNode root) {
	int height = getHeight(root);
	return height < 0 ? 0 : getHeight(root.right) == height - 1 ? (1 << height) + countNodes(root.right) : (1 << (height - 1)) + countNodes(root.left);
}

public int countNodesIterative(TreeNode root) {
	int count = 0, height = getHeight(root);
	while (root != null) {
		if (getHeight(root.right) == height - 1) {
			count += 1 << height;
			root = root.right;
		} else {
			count += 1 << (height - 1);
			root = root.left;
		}
		height--; // don't forget this.
	}
	return count;
}

private int getHeight(TreeNode root) {
	return root == null ? -1 : 1 + getHeight(root.left);
}