Find nodes in binary tree without siblings

Problem

Given a binary tree, return or print all the nodes that do not have siblings. A node does not have a sibling if it is the only child of its parent. If the tree is empty or every node has a sibling, return an empty list or indicate that no such nodes exist.

Examples

Example 1

graph TD;
	A(1) --- B(2) & C(3)
	B --- D(4) & E(5)
	C ~~~ N1:::hidden
	C --- F(6):::ans
	D --- G(7):::ans
	D ~~~ N2:::hidden
	E --- H(8):::ans
	E ~~~ N3:::hidden
	
classDef hidden display:none
classDef ans fill:#1E90FF,stroke:#000,stroke-width:1px,color:#000;

Input: root = [1, 2, 3, 4, 5, null, 6, 7, null, 8, null]
Output: [6, 7, 8]
Explanation: All the nodes in blue dont have siblings and hence part of answer.

Example 2

Input: root = [1, 2, 3]
         1
        / \
       2   3
 
Output: []
 
Explanation: Both child nodes of the root 1 have siblings (2 and 3). Hence, no node exists without siblings.

Example 3

 Input: root = [1, 2, 3, 4]
         1
        / \
       2   3
      /
     4
 
 Output: [4]
 
 Explanation: Node 4 is the only child of its parent (node 2). Other nodes have siblings.

Solution

Method 1 - Preorder Traversal

Here is the approach:

1. Traverse through the binary tree using DFS or BFS.
2. A node does not have a sibling if either of the following conditions is met:
   • The left child is null but the right child exists.
   • The right child is null but the left child exists.
3. If both children exist or both are absent, it means the node has siblings or no children, respectively.
4. Collect all such nodes (nodes without siblings) during traversal.

Code

Java

class Solution {
    public List<Integer> findNodesWithoutSiblings(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        findNodes(root, result);
        return result;
    }

    private void findNodes(TreeNode node, List<Integer> result) {
        if (node == null) return;

        // Check left and right child
        if (node.left != null && node.right == null) {
            result.add(node.left.val);
        } else if (node.right != null && node.left == null) {
            result.add(node.right.val);
        }

        // Recursive calls
        findNodes(node.left, result);
        findNodes(node.right, result);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);

        Solution solution = new Solution();
        System.out.println(solution.findNodesWithoutSiblings(root)); // Output: [4]
    }
}

Python

class Solution:
    def findNodesWithoutSiblings(self, root):
        result = []
        self._find_nodes(root, result)
        return result

    def _find_nodes(self, node, result):
        if not node:
            return
        
        # Check left and right child
        if node.left and not node.right:
            result.append(node.left.val)
        elif node.right and not node.left:
            result.append(node.right.val)

        # Recursive calls for children
        self._find_nodes(node.left, result)
        self._find_nodes(node.right, result)

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)

    solution = Solution()
    print(solution.findNodesWithoutSiblings(root))  # Output: [4]

Complexity

• ⏰ Time complexity: O(n). Every node is visited once during traversal.
• 🧺 Space complexity: O(h). The maximum space used corresponds to the height h of the tree in a recursive implementation or to the breadth in a queue for BFS (O(n) in the worst-case balanced tree as h = log(n)).