Number of half nodes in a binary tree

You're in a Microsoft technical screen and the interviewer pulls up a binary tree on the shared editor. "Given this tree," they say, "can you count the number of nodes that have exactly one child?" It sounds straightforward, but this question probes your ability to define a clean recursive decomposition and handle the base cases correctly. It also opens the door to a neat trick with the XOR operator that most candidates overlook.

TL;DR

Traverse the tree recursively. At each node, use XOR to check whether exactly one child exists: (root.left != null ^ root.right != null). If so, that node is a half node, and you add 1 to the running count. The base case returns 0 for null nodes. This runs in O(n) time and O(h) space where h is the tree height.

Why This Problem Matters

Counting half nodes tests the same recursive tree traversal pattern that shows up in dozens of interview problems: visit a node, compute something locally, combine results from subtrees. Once you internalize this pattern, problems like finding tree height, counting leaves, or computing diameter all follow the same structure. Microsoft and LinkedIn both ask variants of this question to gauge how comfortably you work with tree recursion.

Understanding Half Nodes

Before jumping into the solution, let's clarify the terminology. Every node in a binary tree falls into exactly one of three categories:

• Leaf node: has no children (both left and right are null)
• Half node: has exactly one child (either left or right, but not both)
• Full node: has two children (both left and right are non-null)

Here's a tree that contains all three types:

Node 10 is a full node with two children. Nodes 5 and 15 are half nodes, each with exactly one child. Nodes 3 and 20 are leaves.

The Problem

Given the root TreeNode of a binary tree, return the number of half nodes.

Here's the example from the problem:

Node 3 has only a right child (node 5), making it the sole half node. The answer is 1.

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

Edge Cases

1. Null root: return 0
2. Single node: it's a leaf, so return 0
3. Skewed tree: every node except the leaf is a half node
4. Perfect binary tree: no half nodes at all

Solution Approach

The recursive structure mirrors the tree itself. At each node, ask three things:

1. Is this node null? If so, return 0.
2. Is this node a half node? If it has exactly one child, count 1. Otherwise, count 0.
3. Add the half-node counts from the left and right subtrees.

Detecting Half Nodes with XOR

The interesting part is step 2. You could write it as two separate conditions:

if ((root.left != null && root.right == null) ||
    (root.left == null && root.right != null)) {
    isHalfNode = 1;
}

But the XOR operator handles this more concisely. XOR returns true when exactly one of its operands is true:

• Both null (leaf): false ^ false = false
• Left only (half node): true ^ false = true
• Right only (half node): false ^ true = true
• Both present (full node): true ^ true = false

So (root.left != null ^ root.right != null) is true only for half nodes. Clean and precise.

Implementation

public class Solution {
  public int countHalf(TreeNode root) {
    // Base case: null nodes contribute 0 half nodes
    if (root == null) return 0;

    // XOR: true when exactly one child exists
    int isHalfNode = (root.left != null ^ root.right != null) ? 1 : 0;

    // Combine current result with both subtrees
    return isHalfNode + countHalf(root.left) + countHalf(root.right);
  }
}

Three lines of logic, and the recursion handles the rest. The base case stops at null nodes, the XOR classifies the current node, and the recursive calls aggregate counts from the entire tree.

Tracing Through the Example

Let's trace the recursion on the example tree to see how the count accumulates:

The recursion visits every node exactly once. Node 3 is the only node where XOR evaluates to true, so the final answer is 1.

A Tree with No Half Nodes

Consider a tree where every internal node has two children:

Node 1 has two children (2 and 3). Node 3 has two children (4 and 5). Nodes 2, 4, and 5 are leaves. No node has exactly one child, so countHalf returns 0.

Worst Case: A Skewed Tree

In a completely skewed tree, every node except the leaf has exactly one child:

Here, nodes 1, 2, and 3 are all half nodes. Node 4 is a leaf. The answer is 3. This is also the worst case for space complexity, since the call stack grows to depth n.

Complexity Analysis

Time Complexity: O(n)

Each node is visited exactly once. At each node, the XOR check and the addition are constant-time operations. The total work is proportional to the number of nodes.

Space Complexity: O(h)

The recursion depth equals the height of the tree. For a balanced tree, h = O(log n). For a skewed tree, h = O(n). No auxiliary data structures are used beyond the call stack.

If stack depth is a concern for very deep trees, you can convert this to an iterative solution using an explicit stack or queue, but the recursive version is cleaner and preferred in interviews.

Common Pitfalls

1. Confusing half nodes with leaf nodes: A half node has one child. A leaf has none. The XOR check handles this distinction correctly, but candidates sometimes use || instead of ^ and accidentally count leaves.

2. Forgetting the null base case: Without if (root == null) return 0, the recursion will throw a NullPointerException when it reaches a null child.

3. Using && instead of ^: AND would match only full nodes (both children present), not half nodes.

4. Returning boolean instead of int: The problem asks for a count, not a yes/no answer. Make sure you accumulate across the entire tree.

Interview Tips

When solving this in an interview:

• Start by defining what a half node is. Drawing a small tree and labeling each node as leaf, half, or full shows clear thinking.
• Mention the XOR approach early. It demonstrates familiarity with bitwise operators and produces cleaner code.
• Walk through a 3-4 node example before coding. This catches off-by-one errors and clarifies the recursion.
• After coding, discuss the iterative alternative using a queue (BFS) or stack (DFS). Mentioning tradeoffs shows depth of understanding.

Key Takeaways

• A half node has exactly one child. XOR (^) detects this condition in a single expression by returning true when exactly one operand is true.
• The recursive pattern of "check current node, combine with subtree results" is the same structure used for tree height, leaf count, diameter, and many other tree problems.
• Time complexity is O(n) since every node is visited once. Space complexity is O(h) from the call stack, ranging from O(log n) for balanced trees to O(n) for skewed trees.
• Test with single-node trees (leaf, returns 0), skewed trees (maximum half nodes), and perfect binary trees (zero half nodes) to cover all structural cases.

Related Problems

Once you're comfortable counting half nodes, try these problems that use the same recursive tree traversal pattern:

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

Consistent practice with tree recursion builds the muscle memory that makes these problems feel automatic. This problem and many others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at companies like Microsoft, LinkedIn, Google, and Amazon.

Solutions in Other Languages

Python

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

        is_half_node = 1 if (root.left is not None) ^ (root.right is not None) else 0

        return is_half_node + self.count_half(root.left) + self.count_half(root.right)

JavaScript

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

    const isHalfNode = (root.left !== null ^ root.right !== null) ? 1 : 0;

    return isHalfNode + this.countHalf(root.left) + this.countHalf(root.right);
  }
}

TypeScript

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

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

    return isHalfNode + this.countHalf(root.left) + this.countHalf(root.right);
  }
}

TypeScript lacks a boolean XOR operator, so we use !== on the two boolean expressions instead. The result is identical.

C++

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

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

    return isHalfNode + countHalf(root->left) + countHalf(root->right);
  }
};

Go

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

    var isHalfNode int
    if (root.Left == nil && root.Right != nil) || (root.Left != nil && root.Right == nil) {
        isHalfNode = 1
    }

    return isHalfNode + s.CountHalf(root.Left) + s.CountHalf(root.Right)
}

Go does not have a boolean XOR operator, so the condition is written out as two explicit cases.

Scala

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

    val isHalfNode = if (root.left != null ^ root.right != null) 1 else 0

    isHalfNode + countHalf(root.left) + countHalf(root.right)
  }
}

Kotlin

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

        val isHalfNode = if ((root.left != null) xor (root.right != null)) 1 else 0

        return isHalfNode + countHalf(root.left) + countHalf(root.right)
    }
}

Kotlin uses the xor infix function instead of the ^ operator for boolean XOR.

Swift

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

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

    return isHalfNode + countHalf(root!.left) + countHalf(root!.right)
}

Ruby

def count_half(root)
  return 0 if root.nil?

  is_half_node = (!root.left.nil? ^ !root.right.nil?) ? 1 : 0

  is_half_node + count_half(root.left) + count_half(root.right)
end

Rust

pub fn count_half(&self, root: Option<Box<TreeNode>>) -> i32 {
    Self::count_half_helper(&root)
}

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

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

    is_half_node + Self::count_half_helper(&current.left) + Self::count_half_helper(&current.right)
}

Rust requires a helper method that takes references to avoid ownership issues with the recursive calls.

C#

public int countHalf(TreeNode? root) {
    if (root == null) return 0;

    var isHalfNode = (root.left != null ^ root.right != null) ? 1 : 0;

    return isHalfNode + countHalf(root.left) + countHalf(root.right);
}

Dart

int countHalf(TreeNode? root) {
    if (root == null) return 0;

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

    return isHalfNode + countHalf(root.left) + countHalf(root.right);
}

Dart uses != on booleans for XOR, similar to the TypeScript approach.

PHP

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

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

    return $isHalfNode + $this->countHalf($root->left) + $this->countHalf($root->right);
}

PHP uses the xor keyword for boolean XOR.