Number of full nodes in a binary tree

You're in a Microsoft interview and the interviewer draws a binary tree on the whiteboard. "Count the full nodes," they say. You pause for a moment. Not the leaves. Not all the nodes. Just the ones with both children present. This problem, sometimes called "count complete nodes in a binary tree" on other platforms, is a clean test of whether you understand tree structure and recursive decomposition. It shows up regularly at companies like Microsoft and LinkedIn as a warm-up before harder tree questions.

TL;DR

Traverse the tree recursively. At each node, check whether both left and right children exist. If they do, that node contributes 1 to the count. Add the recursive counts from both subtrees and return the total. The base case returns 0 for a null node. This runs in O(n) time and O(h) space, where h is the tree height.

Why This Problem Matters

Counting full nodes is a straightforward tree traversal problem, but it builds the exact skills you need for harder questions. The pattern of visiting every node, making a local decision, and combining results from subtrees shows up in tree diameter, path sum, balance checking, and dozens of other problems. Get comfortable with this pattern and the harder variants become much more approachable.

Binary Trees: Quick Refresher

A binary tree is a hierarchical structure where each node has at most two children. Here is a small example:

Key terms:

• Root: The topmost node (node 1 here)
• Leaf: A node with no children (nodes 2, 4, and 5)
• Full node: A node with both left and right children
• Half node: A node with only one child

Understanding the Problem

Given: The root of a binary tree Task: Count the number of full nodes Definition: A full node has both a non-null left child and a non-null right child

Looking at our example tree, which nodes are full?

Node 1 has children 2 (left) and 3 (right), so it is full. Node 3 has children 4 (left) and 5 (right), so it is also full. Node 2 is a leaf with no children. Nodes 4 and 5 are also leaves. The answer is 2.

Edge Cases

1. Empty tree (null root): Return 0
2. Single node: No children at all, so 0 full nodes
3. Skewed tree (every node has only one child): 0 full nodes
4. Complete binary tree: Every internal node is full

A single-node tree:

No children, so 0 full nodes.

A skewed tree where every node has only one child:

No node has both children, so 0 full nodes here too.

Solution Approach

The recursive insight is clean. At each node, you need to answer two questions:

1. Is this node full? (Does it have both left and right children?)
2. How many full nodes exist in its left and right subtrees?

The total count at any node is: its own weight (1 if full, 0 if not) plus the recursive count from the left subtree plus the recursive count from the right subtree.

Prefer a different language? Jump to solutions in other languages.

Building Intuition

Think about it from the perspective of each node. You ask your left subtree, "How many full nodes do you have?" Then you ask your right subtree the same question. You add those two numbers together, and if you yourself have both children, you add 1 more. That is the entire algorithm.

Pro tip: This "local decision + combine subtree results" pattern is the backbone of most recursive tree problems. Once you internalize it, problems like tree diameter and maximum path sum become variations on the same theme.

Implementation

Here is the Java solution:

public class Solution {
  public int countFull(TreeNode root) {
    // Base case: empty subtree contributes 0 full nodes
    if (root == null) return 0;

    // Is this node full? 1 if both children exist, 0 otherwise
    int nodeWeight = (root.left != null && root.right != null) ? 1 : 0;

    // Combine: this node's weight + counts from both subtrees
    return nodeWeight + countFull(root.left) + countFull(root.right);
  }
}

Three lines of logic. That is one of the reasons interviewers like this problem. The solution is short, but it reveals whether you understand recursive tree traversal.

Tracing Through the Example

Let's walk through the recursion on our example tree (1, 2, 3, #, #, 4, 5):

The recursion visits every node exactly once. At each leaf, it returns 0. At each internal node, it sums up its own contribution with the results from both subtrees.

Step by step:

1. countFull(1): Node 1 has both children. nodeWeight = 1. Recurse left and right.
2. countFull(2): Node 2 is a leaf. Return 0.
3. countFull(3): Node 3 has both children. nodeWeight = 1. Recurse left and right.
4. countFull(4): Leaf. Return 0.
5. countFull(5): Leaf. Return 0.
6. Back at node 3: 1 + 0 + 0 = 1.
7. Back at node 1: 1 + 0 + 1 = 2.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node, we do constant work: one null check and one conditional. Total work is O(n).

Space Complexity: O(h)

The space comes from the recursive call stack. In the best case (balanced tree), the height h is O(log n). In the worst case (skewed tree), h is O(n). So the space ranges from O(log n) to O(n).

For trees with up to 1000 nodes (as this problem guarantees), recursion is perfectly safe. You will not hit stack overflow.

Iterative Alternative

If the tree were extremely deep, you could use an explicit stack or queue:

public int countFullIterative(TreeNode root) {
    if (root == null) return 0;
    int count = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null && node.right != null) count++;
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return count;
}

Same O(n) time, but the space is now O(w) where w is the maximum width of the tree. For a balanced tree, w can be up to n/2, so this trades stack depth for queue width. In practice, the recursive version is preferred in interviews for its clarity.

Common Pitfalls

1. Checking only one child: A node with just a left child (or just a right child) is not full. You need both.
2. Counting leaves as full: Leaves have zero children. Do not confuse "leaf" with "full."
3. Forgetting the base case: Always handle the null case first in recursive tree code.
4. Confusing full nodes with a full binary tree: A "full binary tree" means every node has 0 or 2 children. This problem just asks you to count the nodes that happen to have 2 children in any tree.

A Neat Property

There is a well-known relationship between full nodes and leaf nodes in any binary tree: the number of leaf nodes is always exactly one more than the number of full nodes. If you count 2 full nodes, there are 3 leaves. You can verify this with our example: nodes 2, 4, and 5 are leaves (3 total), and nodes 1 and 3 are full (2 total). 3 = 2 + 1.

This property is occasionally asked as a follow-up question, so it is worth remembering.

Interview Tips

1. Clarify the definition: Ask the interviewer what "full node" means. Some use the term to mean "has at least one child" rather than "has both children."
2. Start with the base case: Mention root == null returns 0 before anything else.
3. Draw a small tree: Sketch 4-5 nodes and manually count the full nodes to validate your logic.
4. Mention the iterative alternative: Even if you code the recursive version, noting that BFS works too shows breadth of knowledge.
5. Discuss complexity clearly: Mention that the recursion depth depends on tree height, not just node count.

Key Takeaways

• A full node has both left and right children. The recursive formula is nodeWeight + countFull(left) + countFull(right) with nodeWeight being 1 when both children exist.
• Time is O(n) because every node is visited once. Space is O(h) for the call stack, where h ranges from O(log n) for balanced trees to O(n) for skewed trees.
• The "local decision + combine subtrees" pattern used here is the foundation for tree diameter, balance checking, path sums, and many other tree problems.
• Leaf count always equals full node count plus one in any binary tree, a property that occasionally appears as a follow-up.

Practice Makes Perfect

Once you are comfortable counting full nodes, try these related problems to deepen your tree traversal skills:

• Count the leaves of a binary tree
• Find the size of a binary tree
• Height of a binary tree
• Diameter of a binary tree

Solutions in Other Languages

Python

class Solution:
    def count_full(self, root: TreeNode) -> int:
        if root is None:
            return 0

        node_weight = 1 if root.left is not None and root.right is not None else 0

        return node_weight + self.count_full(root.left) + self.count_full(root.right)

JavaScript

class Solution {
  countFull(root) {
    if (root === null) return 0;

    const nodeWeight = (root.left !== null && root.right !== null) ? 1 : 0;

    return nodeWeight + this.countFull(root.left) + this.countFull(root.right);
  }
}

TypeScript

class Solution {
  countFull(root: TreeNode | null): number {
    if (root === null) return 0;

    const nodeWeight = (root.left !== null && root.right !== null) ? 1 : 0;

    return nodeWeight + this.countFull(root.left) + this.countFull(root.right);
  }
}

C++

class Solution {
public:
  int countFull(TreeNode *root) {
    if (root == nullptr)
      return 0;

    int nodeWeight = (root->left != nullptr && root->right != nullptr) ? 1 : 0;

    return nodeWeight + countFull(root->left) + countFull(root->right);
  }
};

Go

func (s *Solution) CountFull(root *TreeNode) int {
	if root == nil {
		return 0
	}

	nodeWeight := 0
	if root.Left != nil && root.Right != nil {
		nodeWeight = 1
	}

	return nodeWeight + s.CountFull(root.Left) + s.CountFull(root.Right)
}

Scala

class Solution {
  def countFull(root: TreeNode): Int = {
    if (root == null) return 0

    val nodeWeight = if (root.left != null && root.right != null) 1 else 0

    nodeWeight + countFull(root.left) + countFull(root.right)
  }
}

Kotlin

class Solution {
  fun countFull(root: TreeNode?): Int {
    if (root == null) return 0

    val nodeWeight = if (root.left != null && root.right != null) 1 else 0

    return nodeWeight + countFull(root.left) + countFull(root.right)
  }
}

Ruby

class Solution
  def count_full(root)
    return 0 if root.nil?

    node_weight = (!root.left.nil? && !root.right.nil?) ? 1 : 0

    node_weight + count_full(root.left) + count_full(root.right)
  end
end

Rust

impl Solution {
    pub fn count_full(&self, root: Option<Box<TreeNode>>) -> i32 {
        Self::count_full_helper(&root)
    }

    fn count_full_helper(node: &Option<Box<TreeNode>>) -> i32 {
        if node.is_none() {
            return 0;
        }
        let current = node.as_ref().unwrap();

        let node_weight = if current.left.is_some() && current.right.is_some() { 1 } else { 0 };

        node_weight + Self::count_full_helper(&current.left) + Self::count_full_helper(&current.right)
    }
}

Swift

class Solution {
    func countFull(_ root: TreeNode?) -> Int {
        if root == nil { return 0 }

        let nodeWeight = (root!.left != nil && root!.right != nil) ? 1 : 0

        return nodeWeight + countFull(root!.left) + countFull(root!.right)
    }
}

Dart

class Solution {
  int countFull(TreeNode? root) {
    if (root == null) return 0;

    int nodeWeight = (root.left != null && root.right != null) ? 1 : 0;

    return nodeWeight + countFull(root.left) + countFull(root.right);
  }
}

PHP

class Solution {
    public function countFull(?TreeNode $root): int {
        if ($root === null) return 0;

        $nodeWeight = ($root->left !== null && $root->right !== null) ? 1 : 0;

        return $nodeWeight + $this->countFull($root->left) + $this->countFull($root->right);
    }
}

C#

public class Solution {
    public int countFull(TreeNode? root) {
        if (root == null) return 0;

        int nodeWeight = (root.left != null && root.right != null) ? 1 : 0;

        return nodeWeight + countFull(root.left) + countFull(root.right);
    }
}

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are warming up with tree basics or grinding through hard graph problems, mastering fundamentals like this will set you up for success.