Facebook | Phone Screen | Count Complete Tree Nodes
Sithis
3735
TreeMetaPhone ScreeningInterview

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

Follow-up:
Given a complete ternary tree, count the number of nodes.

class TreeNode {
	TreeNode left;
	TreeNode mid;
	TreeNode right;
}

Example:

Java solution

For the full ternary tree, say of height h, the number of nodes n is

n = (3^{h+1} - 1) / 2

Why? Because the first level has 3^0 nodes, the second level has 3^1 nodes, and, in general, the k-th level has 3^{k-1} nodes. Adding these up for a total of h+1 levels (so height h) gives

n = 3^0 + 3^1 + 3^2 + 3^3 + ... + 3^h = (3^{h+1} - 1) / (3 - 1) = (3^{h+1} - 1) / 2

public static int countNodes(TreeNode root) {
    int leftHeight = getHeight(root, true);
    int rightHeight = getHeight(root, false);

    if (leftHeight == rightHeight) {
        return (int) (Math.pow(3, leftHeight) - 1) / 2;
    }

    return 1 + countNodes(root.left) + countNodes(root.mid) + countNodes(root.right);
}

private static int getHeight(TreeNode node, boolean left) {
    int h = 0;
    while (node != null) {
        h++;
        node = left ? node.left : node.right;
    }
    return h;
}
Comments (9)