Nodes without Sibling

Last Updated : 30 Mar, 2026

Given a Binary Tree of n nodes, the task is to find all the nodes that don't have any siblings. Return a list of integers containing all the nodes that don't have a sibling in sorted order (Increasing).

Two nodes are said to be siblings if they are present at the same level, and their parents are the same.

Example:

Input:

sibling

Output: 4 5 6

Input:

Balance-a-Binary-Search-Tree

Output: 10 20

Try it on GfG Practice
redirect icon

Table of Content

[Expeacted Approach - 1] Using Recursion - O(nlogn) Time and O(n) Space

The idea is to recursively traverse the binary tree. For each node, if both its child nodes exists, then process both the left and right subtrees. If only left subtree exists, then append its value to the result and process it recursively. If only right subtree exists, then append its value to the result, and process it recursively. Finally sort the resultant array and return it.

Below is the implementation of the above approach:

C++ 
// C++ Program to find nodes with no 
// siblings in a given binary tree
#include <bits/stdc++.h>
using namespace std;
 
class Node {
    public:
        Node *left, *right;
        int data;
        Node(int x) {
            data = x;
            left = nullptr;
            right = nullptr;
        }
};

void noSiblingRecur(Node* node, vector<int> &ans) {
    
    // base case
    if (node == nullptr) return;
    
    // If this is an internal node, recur for left
    // and right subtrees
    if (node->left != nullptr && node->right != nullptr) {
        noSiblingRecur(node->left, ans);
        noSiblingRecur(node->right, ans);
    }
    
    // If only left child exists, then
    // append it to result and recur.
    else if (node->left != nullptr) {
        ans.push_back(node->left->data);
        noSiblingRecur(node->left, ans);
    }
    
    // If only right child exists, then
    // append it to result and recur.
    else if (node->right != nullptr) {
        ans.push_back(node->right->data);
        noSiblingRecur(node->right, ans);
    }
}

vector<int> noSibling(Node* node) {
        
    vector<int> ans;
    
    noSiblingRecur(node, ans);
    
    // if there are 0 nodes
    // without any siblings
    if (ans.empty())
        ans.push_back(-1);
    
    // else sort the result
    else
        sort(ans.begin(), ans.end());
    
    return ans;
}

void printList(vector<int> v) {
    int n = v.size();
    for (int i=0; i<n; i++) {
        cout << v[i] << " ";
    }
    cout<<endl;
}
 
int main() {
    
    // Create a hard coded binary tree
    //        1
    //      /   \
    //     2     3            
    //      \   /
    //      4  5     
    //        /
    //       6
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(5);
    root->right->left->left = new Node(6);
    
    vector<int> ans = noSibling(root);
    printList(ans);
    
    return 0;
}
Java 
// Java Program to find nodes with no
// siblings in a given binary tree
import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {
    static void noSiblingRecur(Node node, ArrayList<Integer> ans) {
        
        // base case
        if (node == null) return;

        // If this is an internal node, recur for left
        // and right subtrees
        if (node.left != null && node.right != null) {
            noSiblingRecur(node.left, ans);
            noSiblingRecur(node.right, ans);
        }

        // If only left child exists, then
        // append it to result and recur.
        else if (node.left != null) {
            ans.add(node.left.data);
            noSiblingRecur(node.left, ans);
        }

        // If only right child exists, then
        // append it to result and recur.
        else if (node.right != null) {
            ans.add(node.right.data);
            noSiblingRecur(node.right, ans);
        }
    }
    
    static ArrayList<Integer> noSibling(Node node) {
        
        ArrayList<Integer> ans = new ArrayList<Integer>();

        noSiblingRecur(node, ans);

        // if there are 0 nodes
        // without any siblings
        if (ans.isEmpty())
            ans.add(-1);

        // else sort the result
        else
            Collections.sort(ans);

        return ans;
    }
    
    static void printList(ArrayList<Integer> v) {
        for (int i : v) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        
        // Create a hard coded binary tree
        //        1
        //      /   \
        //     2     3
        //      \   /
        //      4  5
        //        /
        //       6
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.left = new Node(6);

        ArrayList<Integer> ans = noSibling(root);
        printList(ans);
    }
}
Python 
# Python Program to find nodes with no
# siblings in a given binary tree

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def noSiblingRecur(node, ans):
    
    # base case
    if not node:
        return

    # If this is an internal node, recur for left
    # and right subtrees
    if node.left and node.right:
        noSiblingRecur(node.left, ans)
        noSiblingRecur(node.right, ans)

    # If only left child exists, then
    # append it to result and recur.
    elif node.left:
        ans.append(node.left.data)
        noSiblingRecur(node.left, ans)

    # If only right child exists, then
    # append it to result and recur.
    elif node.right:
        ans.append(node.right.data)
        noSiblingRecur(node.right, ans)
    
def noSibling(node):
    
    ans = []

    noSiblingRecur(node, ans)

    # if there are 0 nodes
    # without any siblings
    if not ans:
        ans.append(-1)

    # else sort the result
    else:
        ans.sort()

    return ans

def printList(v):
    print(" ".join(map(str, v)))

if __name__ == "__main__":
    
    # Create a hard coded binary tree
    #        1
    #      /   \
    #     2     3
    #      \   /
    #      4  5
    #        /
    #       6
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.right = Node(4)
    root.right.left = Node(5)
    root.right.left.left = Node(6)

    ans = noSibling(root)
    printList(ans)
C# 
// C# Program to find nodes with no
// siblings in a given binary tree
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {
    static void NoSiblingRecur(Node node, List<int> ans) {
        
        // base case
        if (node == null) return;

        // If this is an internal node, recur for left
        // and right subtrees
        if (node.left != null && node.right != null) {
            NoSiblingRecur(node.left, ans);
            NoSiblingRecur(node.right, ans);
        }

        // If only left child exists, then
        // append it to result and recur.
        else if (node.left != null) {
            ans.Add(node.left.data);
            NoSiblingRecur(node.left, ans);
        }

        // If only right child exists, then
        // append it to result and recur.
        else if (node.right != null) {
            ans.Add(node.right.data);
            NoSiblingRecur(node.right, ans);
        }
    }

    static List<int> NoSibling(Node node) {
        
        List<int> ans = new List<int>();

        NoSiblingRecur(node, ans);

        // if there are 0 nodes
        // without any siblings
        if (ans.Count == 0)
            ans.Add(-1);

        // else sort the result
        else
            ans.Sort();

        return ans;
    }
    
    static void PrintList(List<int> v) {
        foreach (int i in v) {
            Console.Write(i + " ");
        }
        Console.WriteLine();
    }

    static void Main(string[] args) {
        
        // Create a hard coded binary tree
        //        1
        //      /   \
        //     2     3
        //      \   /
        //      4  5
        //        /
        //       6
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.left = new Node(6);

        List<int> ans = NoSibling(root);
        PrintList(ans);
    }
}
JavaScript 
// JavaScript Program to find nodes with no
// siblings in a given binary tree

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function noSiblingRecur(node, ans) {
    
    // base case
    if (!node) return;

    // If this is an internal node, recur for left
    // and right subtrees
    if (node.left && node.right) {
        noSiblingRecur(node.left, ans);
        noSiblingRecur(node.right, ans);
    }

    // If only left child exists, then
    // append it to result and recur.
    else if (node.left) {
        ans.push(node.left.data);
        noSiblingRecur(node.left, ans);
    }

    // If only right child exists, then
    // append it to result and recur.
    else if (node.right) {
        ans.push(node.right.data);
        noSiblingRecur(node.right, ans);
    }
}

function noSibling(node) {
    
    let ans = [];

    noSiblingRecur(node, ans);

    // if there are 0 nodes
    // without any siblings
    if (ans.length === 0)
        ans.push(-1);

    // else sort the result
    else
        ans.sort((a, b) => a - b);

    return ans;
}

function printList(v) {
    console.log(v.join(" "));
}

// Create a hard coded binary tree
//        1
//      /   \
//     2     3
//      \   /
//      4  5
//        /
//       6
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.left.left = new Node(6);

const ans = noSibling(root);
printList(ans);

Output
4 5 6

Time Complexity: O(nlogn), time taken to sort the resultant array.
Space Complexity:O(n), where n is the number of nodes in tree.

[Expected Approach - 2] Using Queue - O(nlogn) Time and O(n) Space

The idea is to use level order traversal to traverse the nodes. For each node, If both its child nodes exists, then push both the nodes into the queue. If one of the child nodes exists, then append the child node into the resultant list and push it into the queue.

Below is the implementation of the above approach:

C++ 
// C++ Program to find nodes with no 
// siblings in a given binary tree
#include <bits/stdc++.h>
using namespace std;
 
class Node {
    public:
        Node *left, *right;
        int data;
        Node(int x) {
            data = x;
            left = nullptr;
            right = nullptr;
        }
};

vector<int> noSibling(Node* node) {
    
    if (node == nullptr)
        return {-1};
    
    // create an empty result array
    vector<int> ans;
    
    queue<Node*> q;
    q.push(node);
    
    while (!q.empty()) {
        
        Node* curr = q.front();
        q.pop();
        
        // If this is an internal node, push the left
        // and right nodes into queue
        if (curr->left != nullptr && curr->right != nullptr) {
            q.push(curr->left);
            q.push(curr->right);
        }
     
        // If left child is NULL and right is not, 
        // append right node into result and push
        // it into queue.
        else if (curr->right != nullptr) {
            ans.push_back(curr->right->data);
            q.push(curr->right);
        }
     
        // If right child is NULL and left is 
        // not, append left child to result
        // and push left node into queue.
        else if (curr->left != nullptr) {
            ans.push_back(curr->left->data);
            q.push(curr->left);
        }
    }
    
    // if there are 0 nodes
    // without any siblings
    if (ans.empty())
        ans.push_back(-1);
    
    // else sort the result
    else
        sort(ans.begin(), ans.end());
    
    return ans;
}

void printList(vector<int> v) {
    int n = v.size();
    for (int i=0; i<n; i++) {
        cout << v[i] << " ";
    }
    cout<<endl;
}
 
int main() {
    
    // Create a hard coded binary tree
    //        1
    //      /   \
    //     2     3            
    //      \   /
    //      4  5     
    //        /
    //       6
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->right = new Node(4);
    root->right->left = new Node(5);
    root->right->left->left = new Node(6);
    
    vector<int> ans = noSibling(root);
    printList(ans);
    
    return 0;
}
Java 
// Java Program to find nodes with no
// siblings in a given binary tree
import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {

    static ArrayList<Integer> noSibling(Node node) {
        if (node == null)
            return new ArrayList<>(Arrays.asList(-1));

        // create an empty result array
        ArrayList<Integer> ans = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        q.add(node);

        while (!q.isEmpty()) {
            Node curr = q.poll();

            // If this is an internal node, push the left
            // and right nodes into queue
            if (curr.left != null && curr.right != null) {
                q.add(curr.left);
                q.add(curr.right);
            }

            // If left child is NULL and right is not, 
            // append right node into result and push
            // it into queue.
            else if (curr.right != null) {
                ans.add(curr.right.data);
                q.add(curr.right);
            }

            // If right child is NULL and left is 
            // not, append left child to result
            // and push left node into queue.
            else if (curr.left != null) {
                ans.add(curr.left.data);
                q.add(curr.left);
            }
        }

        // if there are 0 nodes
        // without any siblings
        if (ans.isEmpty())
            ans.add(-1);

        // else sort the result
        else
            Collections.sort(ans);

        return ans;
    }

    static void printList(ArrayList<Integer> v) {
        for (int i : v) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
      
        // Create a hard coded binary tree
        //        1
        //      /   \
        //     2     3
        //      \   /
        //      4  5
        //        /
        //       6
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.left = new Node(6);

        ArrayList<Integer> ans = noSibling(root);
        printList(ans);
    }
}
Python 
# Python Program to find nodes with no
# siblings in a given binary tree
from queue import Queue

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def noSibling(node):
    if not node:
        return [-1]

    # create an empty result array
    ans = []
    q = Queue()
    q.put(node)

    while not q.empty():
        curr = q.get()

        # If this is an internal node, push the left
        # and right nodes into queue
        if curr.left and curr.right:
            q.put(curr.left)
            q.put(curr.right)

        # If left child is NULL and right is not, 
        # append right node into result and push
        # it into queue.
        elif curr.right:
            ans.append(curr.right.data)
            q.put(curr.right)

        # If right child is NULL and left is 
        # not, append left child to result
        # and push left node into queue.
        elif curr.left:
            ans.append(curr.left.data)
            q.put(curr.left)

    # if there are 0 nodes
    # without any siblings
    if not ans:
        ans.append(-1)

    # else sort the result
    else:
        ans.sort()

    return ans

def printList(v):
    print(" ".join(map(str, v)))

if __name__ == "__main__":
    
    # Create a hard coded binary tree
    #        1
    #      /   \
    #     2     3
    #      \   /
    #      4  5
    #        /
    #       6
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.right = Node(4)
    root.right.left = Node(5)
    root.right.left.left = Node(6)

    ans = noSibling(root)
    printList(ans)
C# 
// C# Program to find nodes with no
// siblings in a given binary tree
using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GfG {
    static List<int> NoSibling(Node node) {
        if (node == null)
            return new List<int> { -1 };

        // create an empty result array
        List<int> ans = new List<int>();
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(node);

        while (q.Count > 0) {
            Node curr = q.Dequeue();

            // If this is an internal node, push the left
            // and right nodes into queue
            if (curr.left != null && curr.right != null) {
                q.Enqueue(curr.left);
                q.Enqueue(curr.right);
            }

            // If left child is NULL and right is not, 
            // append right node into result and push
            // it into queue.
            else if (curr.right != null) {
                ans.Add(curr.right.data);
                q.Enqueue(curr.right);
            }

            // If right child is NULL and left is 
            // not, append left child to result
            // and push left node into queue.
            else if (curr.left != null) {
                ans.Add(curr.left.data);
                q.Enqueue(curr.left);
            }
        }

        // if there are 0 nodes
        // without any siblings
        if (ans.Count == 0)
            ans.Add(-1);

        // else sort the result
        else
            ans.Sort();

        return ans;
    }

    static void PrintList(List<int> v) {
        foreach (int i in v) {
            Console.Write(i + " ");
        }
        Console.WriteLine();
    }

    static void Main(string[] args) {
        
        // Create a hard coded binary tree
        //        1
        //      /   \
        //     2     3
        //      \   /
        //      4  5
        //        /
        //       6
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.left = new Node(6);

        List<int> ans = NoSibling(root);
        PrintList(ans);
    }
}
JavaScript 
// JavaScript Program to find nodes with no
// siblings in a given binary tree

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function noSibling(node) {
    if (node === null)
        return [-1];

    // create an empty result array
    const ans = [];
    const q = [];
    q.push(node);

    while (q.length > 0) {
        let curr = q.shift();

        // If this is an internal node, push the left
        // and right nodes into queue
        if (curr.left !== null && curr.right !== null) {
            q.push(curr.left);
            q.push(curr.right);
        }

        // If left child is NULL and right is not, 
        // append right node into result and push
        // it into queue.
        else if (curr.right !== null) {
            ans.push(curr.right.data);
            q.push(curr.right);
        }

        // If right child is NULL and left is 
        // not, append left child to result
        // and push left node into queue.
        else if (curr.left !== null) {
            ans.push(curr.left.data);
            q.push(curr.left);
        }
    }

    // if there are 0 nodes
    // without any siblings
    if (ans.length === 0)
        ans.push(-1);

    // else sort the result
    else
        ans.sort((a, b) => a - b);

    return ans;
}

function printList(v) {
    console.log(v.join(" "));
}

// Create a hard coded binary tree
//        1
//      /   \
//     2     3
//      \   /
//      4  5
//        /
//       6
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.left.left = new Node(6);

const ans = noSibling(root);
printList(ans);

Output
4 5 6

Time Complexity: (nlogn), time taken to sort the resultant array.
Auxiliary Space: O(n), where n is the number of nodes in tree.

Comment
Article Tags:
Tree
DSA
Amazon
D-E-Shaw

Explore