Count Single-Child Nodes — Problem Statement & Solution Guide
Problem Description
You are provided with the root node of a binary tree. Your task is to determine the count of nodes that possess exactly one non-null child. In a binary tree, a node may have zero, one, or two children. A node is considered to have a single child if either its left pointer is null and its right pointer is non-null, or its left pointer is non-null and its right pointer is null. Nodes with two children (internal nodes) and nodes with no children (leaf nodes) do not contribute to this count.
The input will be the root of a binary tree. You must return an integer representing the total number of such single-child nodes in the entire tree. If the tree is empty (root is null), the count is zero.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Single-Child Nodes"
WHY DOES IT MATTER?
Counting single‑child nodes is a classic example of a local‑property aggregation problem on trees, a pattern that recurs in many real‑world scenarios such as detecting imbalanced branches in file systems, identifying nodes with missing configuration, or optimizing memory layout in compiler ASTs.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the single‑child condition is independent of deeper sub‑tree structure, allowing a single linear traversal with an accumulator instead of nested scans, thus collapsing O(n^2) work into O(n).
REAL-WORLD CONNECTION
Think of a corporate org chart where each manager may have zero, one, or two direct reports. Counting managers with exactly one report helps spot potential bottlenecks or under‑utilized leadership roles, analogous to counting single‑child nodes in a binary tree.
When coding this in an interview, start with a clean recursive DFS skeleton, add the local check, and remember to handle null roots early; this keeps the solution concise and avoids off‑by‑one errors.
COMPLEXITY AT A GLANCE
O(n)O(h) recursive stack or O(n) for iterative queueCore Theory — Why This Approach?
In a binary tree each node can have zero, one, or two children. The problem asks for the number of nodes that have exactly one non‑null child, often called "single‑child" nodes. A straightforward way to obtain this count is to traverse the entire tree (pre‑order, in‑order, post‑order, or level‑order) and inspect the left and right pointers of every visited node. If one pointer is null while the other is not, we increment a global counter. Naïve approaches that repeatedly search sub‑trees for each node or that rebuild the tree structure lead to O(n^2) time on skewed trees because each node may be visited many times. The optimal paradigm leverages a single depth‑first search (DFS) or breadth‑first search (BFS) pass, guaranteeing each node is examined exactly once, yielding linear time O(n) where n is the number of nodes. This approach also uses only O(h) auxiliary space for recursion (h = tree height) or O(n) for an explicit queue in BFS, both of which are optimal for tree traversal problems.
The key insight is that the property "exactly one child" is a local condition that can be evaluated independently at each node without needing information from its ancestors or descendants beyond the immediate children. Therefore, a simple accumulator pattern during traversal suffices. Recursive DFS is particularly elegant: the function returns the count for the subtree rooted at the current node, adds one if the current node meets the single‑child criterion, and propagates the sum upward. Iterative BFS achieves the same effect with a queue, which can be preferable in environments where recursion depth may cause stack overflow.
Why naive solutions fail on large inputs is rooted in their repeated work. For example, scanning the entire tree for each node to check its children results in O(n^2) time, which becomes prohibitive for trees with millions of nodes. By contrast, the optimal single‑pass traversal scales linearly, making it suitable for production‑grade systems that process massive hierarchical data structures such as file systems, organizational charts, or distributed configuration trees.
Interview Questions on This Problem
Q1How would you modify the algorithm to also return the list of nodes that have exactly one child?
During the traversal, instead of only incrementing a counter, push the current node (or its value) onto a result list whenever the single‑child condition holds. At the end of the DFS/BFS, return both the count (list length) and the list itself.
Q2Can you compute the count of single‑child nodes in O(1) extra space without using recursion or an explicit queue?
Yes, by performing Morris inorder traversal which temporarily rewires the tree to create threaded links, we can visit each node in O(1) auxiliary space while still checking the child pointers and updating the count.
Q3In a distributed system where each node of a binary tree resides on a different server, how would you aggregate the count of single‑child nodes efficiently?
Each server computes the count for its local subtree and returns the result to a coordinator. The coordinator aggregates the partial counts using a reduce operation, achieving O(log k) communication steps for k servers, while each server still runs a linear‑time local traversal.
Examples
Input
root = [1, 2, 3, null, 4, null, null]
Output
0
Explanation: The tree structure is: Node 1 has left child 2 and right child 3 (2 children, not counted). Node 2 has no left child and right child 4 (1 child, counted). Node 3 has no children (0 children, not counted). Node 4 has no children (0 children, not counted). Total count is 1.
Input
root = [5, 6, 7, 8, null, null, 9]
Output
0
Explanation: Node 5 has left child 6 and right child 7 (2 children, not counted). Node 6 has left child 8 and no right child (1 child, counted). Node 7 has no left child and right child 9 (1 child, counted). Node 8 is a leaf (0 children, not counted). Node 9 is a leaf (0 children, not counted). Total count is 2.
Input
root = [10, null, 20, null, 30]
Output
0
Explanation: Node 10 has no left child and right child 20 (1 child, counted). Node 20 has no left child and right child 30 (1 child, counted). Node 30 is a leaf (0 children, not counted). Total count is 2.
Input
root = [1, 2, 3, 4, 5, 6, 7]
Output
0
Explanation: Node 1 has left child 2 and right child 3 (2 children, not counted). Node 2 has left child 4 and right child 5 (2 children, not counted). Node 3 has left child 6 and right child 7 (2 children, not counted). Nodes 4, 5, 6, 7 are leaves (0 children, not counted). Total count is 0.
Constraints
- The number of nodes in the tree is in the range [0, 10^5].
- -10^9 <= Node.val <= 10^9.
- The tree is a valid binary tree.
- The depth of the tree will not exceed 10^5.
Optimal Approach & Strategy
Perform a single DFS or BFS pass, checking the child pointers of each node exactly once and accumulating the count, achieving O(n) time.
Brute Force Approach
Repeatedly scan the entire tree for each node to see if it has exactly one child, leading to O(n^2) time. This double‑loop approach revisits nodes many times.
Verified Code Solutions
function dfs(node){
if(!node) return 0;
let cnt = 0;
if((node.left===null) !== (node.right===null)) cnt = 1;
return cnt + dfs(node.left) + dfs(node.right);
}
function countSingleChildNodes(root){return dfs(root);}#include <bits/stdc++.h>
using namespace std;
struct TreeNode{int val; TreeNode* left; TreeNode* right; TreeNode(int x):val(x),left(nullptr),right(nullptr){}}
;
int dfs(TreeNode* node){
if(!node) return 0;
int cnt = 0;
if((node->left==nullptr) ^ (node->right==nullptr)) cnt = 1;
return cnt + dfs(node->left) + dfs(node->right);
}
int countSingleChildNodes(TreeNode* root){return dfs(root);}public class Solution {
private int dfs(TreeNode node){
if(node==null) return 0;
int cnt = ((node.left==null) ^ (node.right==null)) ? 1 : 0;
return cnt + dfs(node.left) + dfs(node.right);
}
public int countSingleChildNodes(TreeNode root){
return dfs(root);
}
}
def dfs(node):
if not node:
return 0
cnt = 1 if (node.left is None) ^ (node.right is None) else 0
return cnt + dfs(node.left) + dfs(node.right)
def countSingleChildNodes(root: TreeNode) -> int:
return dfs(root)function dfs(node){
if(!node) return 0;
let cnt = 0;
if((node.left===null) !== (node.right===null)) cnt = 1;
return cnt + dfs(node.left) + dfs(node.right);
}
function countSingleChildNodes(root){return dfs(root);}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.