The idea here is to use the fact that if a node of the binary tree has two child nodes, then both of them will be siblings to each other, and if a node of the binary tree has only one child, then that child will not have any sibling.

Example 

In above figure 1 has two children, so nodes 3 and 4 are siblings to each other. Also, 3 has only one child, i.e., 5 and 5 have no sibling node.

So, we will use a dfs function to find all the nodes that have a single child.

Algorithm :

• Declare an empty array say, ‘answer’ to store all the nodes that don’t have a sibling node.
• Call dfs function to store all nodes that don’t have a sibling in ‘answer’ array.
• Sort the ‘answer’.
• Finally, return the ‘answer’.

Description of DFS function

This function will take two arguments, first one is ‘node’, which denotes the current node, and second is the array ‘answer’ to store all the nodes that don’t have a sibling.

DFS(node, ‘answer’) : 

• If ‘node’ equals NULL, then return.
• If both left and right child of ‘node’ is not NULL, then recur for ‘node -> left’ and ‘node -> right’.
• Else two conditions will occur:
• If the right child of ‘node’ is not NULL, then add data of the right child to ‘answer’ and recur for ‘node ->right’.
• If the left child of ‘node’ is not NULL, then add data of the left child to ‘answer’ and recur for ‘node -> left’.
• If both, left and right child of a node are NULL, then break the recursion.

O(N), where ‘N’ is the total number of nodes in the given binary tree.

In the worst case, when we have given a skew binary tree, we need O(N) extra space in the form of recursive calls.

Hence the overall space complexity will be O(N).

O(N), where ‘N’ is the total number of nodes in the given binary tree.

In the worst case, we visit each node exactly once in the DFS function that takes O(N) time.

Hence, the overall time complexity will be O(N).

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the total number of nodes in the binary tree.

'''



# DFS function to store all nodes that don't have a sibling.

def dfs(node, answer):

    if node == None:

        return

    

    # Store all single child nodes.

    if node.left != None and node.right != None:

        dfs(node.left, answer)

        dfs(node.right, answer)

    

    elif node.left != None:

        answer.append(node.left.val)

        dfs(node.left, answer)

        

    elif node.right != None:

        answer.append(node.right.val)

        dfs(node.right, answer)



def siblingNodes(node):

    answer = []

    

    if node == None:

        return answer

    

    dfs(node, answer)

    

    # Sort the answer.

    answer.sort()

    

    return answer

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the total number of nodes in the binary tree.

*/



#include 



// DFS function to store all nodes that don't have a sibling.

void dfs(TreeNode *node, vector &answer)

{

    // Base case

    if (node == NULL)

    {

        return;

    }



    // Store all single child nodes.

    if (node->left != NULL and node->right != NULL)

    {

        dfs(node->left, answer);

        dfs(node->right, answer);

    }

    else if (node->left != NULL)

    {

        answer.push_back(node->left->val);

        dfs(node->left, answer);

    }

    else if (node->right != NULL)

    {

        answer.push_back(node->right->val);

        dfs(node->right, answer);

    }

}



vector siblingNodes(TreeNode *node)

{

    vector answer;



    if (node == NULL)

    {

        return answer;

    }



    dfs(node, answer);



    // Sort the answer.

    sort(answer.begin(), answer.end());



    return answer;

}

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the total number of nodes in the binary tree.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    // DFS function to store all nodes that don't have a sibling.

    public static void dfs(TreeNode node, ArrayList answer){

        // Base case

        if (node == null){

            return;

        }



        // Store all single child nodes.

        if (node.left != null &&node.right != null){

            dfs(node.left, answer);

            dfs(node.right, answer);

        }

        else if (node.left != null){

            answer.add(node.left.data);

            dfs(node.left, answer);

        }

        else if (node.right != null){

            answer.add(node.right.data);

            dfs(node.right, answer);

        }

    }

    

	public static ArrayList siblingNodes(TreeNode root) {

		ArrayList answer = new ArrayList();



        if (root == null){

            return answer;

        }



        dfs(root, answer);



        // Sort the answer.

        Collections.sort(answer);



        return answer;

	}

}

The idea here is to use a breadth-first search. We will calculate all single-child nodes using BFS. 

Algorithm : 

• Declare an empty array say, ‘answer’ to store all nodes that don’t have a sibling node.
• Declare an empty queue and push the root node of the binary tree to it.
• Run a loop until the queue is not empty.
• Pop the front element from the queue, say ‘current’.
• If both, left and the right child of ‘node’ are not NULL, then push ‘node -> left’ and ‘node -> right’ in the queue.
• Else two conditions will occur:
• If the right child of ‘node’ is not NULL, then add data of the right child to ‘answer’ and push ‘node -> right’ in the queue.
• If the left child of ‘node’ is not NULL, then add data of the left child to ‘answer’ and push ‘node -> left’ in the queue.
• Sort the ‘answer’.
• Finally, return the ‘answer’.

O(N), where ‘N’ is the total number of nodes in the given binary tree.

In the worst case, we are using a queue that requires additional O(N) space as there can be O(N) nodes in the queue in the worst case.

So, the overall space complexity is O(N).

O(N), where ‘N’ is the total number of nodes in the given binary tree.

We are visiting each node exactly once and it takes O(N) time.

Hence, the overall time complexity will be O(N).

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the total number of nodes in the binary tree.

*/



#include 



vector siblingNodes(TreeNode *node)

{

    vector answer;



    if (node == NULL)

    {

        return answer;

    }

    queue *> q;

    q.push(node);



    // Run a loop until queue is not empty.

    while (q.empty() == false)

    {

        TreeNode *current = q.front();

        q.pop();



        // Push single child node to queue.

        if (current->left != NULL and current->right != NULL)

        {

            q.push(current->left);

            q.push(current->right);

        }

        else if (current->left != NULL)

        {

            answer.push_back(current->left->val);

            q.push(current->left);

        }

        else if (current->right != NULL)

        {

            answer.push_back(current->right->val);

            q.push(current->right);

        }

    }



    // Sort the answer.

    sort(answer.begin(), answer.end());



    return answer;

}

'''

    Time Complexity: O(N)

    Space Complexity: O(N)

    

    where N is the number of nodes in the binary tree.

'''



from collections import deque



def siblingNodes(node):

    answer = []

    

    if node == None:

        return answer

    

    q = deque()

    q.append(node)

    

    # Run a loop until the queue is not empty.

    while len(q):

        current = q.popleft()

        

        if current.left != None and current.right != None:

            q.append(current.left)

            q.append(current.right)

            

        elif current.left != None:

            answer.append(current.left.val)

            q.append(current.left)

        

        elif current.right != None:

            answer.append(current.right.val)

            q.append(current.right)

    

    # Sort the answer.

    answer.sort()

    

    return answer

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the total number of nodes in the binary tree.

*/



import java.util.ArrayList;

import java.util.Collections;

import java.util.LinkedList;

import java.util.Queue;



public class Solution {

    

	public static ArrayList siblingNodes(TreeNode root) {

		ArrayList answer = new ArrayList();



        if (root == null){

            return answer;

        }



        Queue> q = new LinkedList<>();

        q.add(root);



        // Run a loop until queue is not empty.

        while (q.isEmpty() == false){

            TreeNode current = q.poll();



            // Push single child node to queue.

            if (current.left != null && current.right != null){

                q.add(current.left);

                q.add(current.right);

            }

            else if (current.left != null){

                answer.add(current.left.data);

                q.add(current.left);

            }

            else if (current.right != null){

                answer.add(current.right.data);

                q.add(current.right);

            }

        }



        // Sort the answer.

        Collections.sort(answer);



        return answer;

	}

}