Divide and Conquer (binary search) Java solution (beats 80%) with comments

• So the idea is the following:

First check if we have a complete filled tree, if yes we know how much nodes we have: `2^h - 1` where `h` is the height of the tree.

Otherwise we know that the number of nodes = `2^(h-1) - 1 + lastLevel`, where `lastLevel` is the number of leafes on the last level.

To get the number of nodes on the last level, we do a D&C logic: first check if there is a middle node on the last level: Basically get the height of the most right node from the left of the current node. If the `mh` height of that node equals to `h` we have middle node otherwise not.

• if we have a middle node on the last level, we need to count on the right side + we know that on the left we had `(1 << (h-2))`.
• if there is no middle, we know that we have less then `(1 << (h-2))` bottom nodes, and we continue our search on the left side.
``````public class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;

// get the height of the most left node
TreeNode current = root;
int lh = 1;
while((current = current.left) != null) lh++;

// get the height of the most right node
current = root;
int rh = 1;
while((current = current.right) != null) rh++;

// if the left and right heights are the same, we have the last level filled,
// so: N = 2^h - 1
if(lh == rh) return (1 << lh) - 1;

// otherwise N = 2^(h-1) - 1 + <number of leaves>
return (1 << rh) - 1 + lastLevel(root, lh);
}

private int lastLevel(TreeNode root, int h) {
// if the height is 1, we have only 1 node
if(h == 1) {
return 1;
} else if(h == 2) {
// if the height is 2, we check left and right to count the last level nodes: 0, 1 or 2
return root.left == null ? 0 : (root.right != null ? 2 : 1);
}

// divide and conquer, first we find the 'middle' node on the last level
TreeNode mid = root.left;
int mh = 2;
while((mid = mid.right) != null) mh++;

if(mh == h) {
// we do have a middle node, so we know that the number of nodes on the last level=
// the number bottom nodes on the left side which is: (1 << (h-2))
// + the number of bottom nodes on the right side
return (1 << (h-2)) + lastLevel(root.right, h-1);
} else {
// if there is no middle node, we know that we must count them on the left side
return lastLevel(root.left, h-1);
}
}
}
``````

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