Print All Nodes of Binary Tree That Do not Have Siblings

by · January 26, 2021

“Print All Nodes of Binary Tree That Do not Have Siblings” is one of foremost algorithmic problem asked in a technical interview of product-based companies. Here, we are given a binary tree and our task is to write a program to print all nodes of binary tree that don’t have siblings.

Sibling Nodes: Two Nodes are said to be sibling nodes if the parent node of both nodes is same. Any Node can have at most one sibling. Root node does not have any sibling.

Print All Nodes of Binary Tree That Don’t Have Siblings

We can solve the following problem both recursively and iteratively. Here, the idea is that for any node (not leaf node), check if it has only one child node or have both child nodes. If only one child node is present, then print that node and continue traversal. If both child nodes are present, then simply continue traversal.

METHOD 1: Recursive Solution

C++ Program to print all nodes of Binary Tree that do not have siblings is as follows:

/* C++ Program to print all nodes of Binary Tree that do not have siblings */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to print all nodes of Binary Tree that don’t have siblings */
void printSingleSiblings(Node *root)
{
    /* Bssic Case: Null Tree */
    if(root == NULL)
    return;
    
    /* If only right child is present, print it and recursively traversel right subtree */
    if(root -> left == NULL && root -> right != NULL)
    {
        cout<<root -> right -> data<<" ";
        printSingleSiblings(root -> right);
    }
    
    /* If only left child is present, print it and recursively traversel left subtree */
    else if(root -> left != NULL && root -> right == NULL)
    {
        cout<<root -> left -> data<<" ";
        printSingleSiblings(root -> left);
    }
    
    /* If both childs are present, recursively traverse them */
    else
    {
        printSingleSiblings(root -> left);
        printSingleSiblings(root -> right);
    }
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
  
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to print all nodes of Binary Tree that do not have siblings */
    cout<<"Nodes in a tree that don't have siblings are:\n";
    printSingleSiblings(root);
}

OUTPUT:

Nodes in a tree that don't have siblings are:
8 9

METHOD 2: Iterative Solution

C++ Program to print all nodes of Binary Tree that do not have siblings is as follows:

/* C++ Program to print all nodes of Binary Tree that do not have siblings */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to print all nodes of Binary Tree that do not have siblings */
void printSingleSiblings(Node *root)
{
    /* Bssic Case: Null Tree */
    if(root == NULL)
    return;
    
   queue<Node *> que;
   que.push(root);
   
   while(!que.empty())
   {
       Node *temp = que.front();
       
       que.pop();
       
       if(temp -> left == NULL && temp -> right != NULL)
       {
           cout<<temp -> right -> data<<" ";
           que.push(temp -> right);
       }
       else if(temp -> left != NULL && temp -> right == NULL)
       {
           cout<<temp -> left -> data<<" ";
           que.push(temp -> left);
       }
       else if(temp -> left != NULL && temp -> right != NULL)
       {
           que.push(temp -> left);
           que.push(temp -> right);
       }
   }
}

int main()
{
    /* Creating a Binary trees and inserting some nodes in it */
    Node *root = NULL;
  
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to print all nodes of Binary Tree that do not have siblings */
    cout<<"Nodes in a tree that don't have siblings are:\n";
    printSingleSiblings(root);
}

OUTPUT:

Nodes in a tree that don't have siblings are:
8 9

Related Posts:

  1. Print All Leaf Nodes of a Binary Tree
  2. Count Number of Nodes in a Binary Tree
  3. Print Alternate Levels of Binary Tree
  4. Maximum Width of Binary Tree
  5. Level Order Tree Traversal
  6. Left View of Binary Tree
  7. Right View of Binary Tree
  8. Compute Height of Binary Tree
  9. Inorder Tree Traversal Using Stack
  10. Preorder Tree Trasversal Using Stack
  11. Postorder Tree Traversal Using Stack
  12. Vertical Order Tree Traversal
  13. Top View of Binary Tree
  14. Bottom View of Binary Tree
  15. Delete Complete Binary Tree
  16. Check if two trees are mirror Trees of Each Other
  17. Convert Binary Tree to its Mirror Tree
  18. Check if Binary Tree is Symmetric or Not
  19. Print All Root to Leaf Paths in a Binary Tree
  20. Determine if two binary trees are identical or not

You may also like...