Print Cousins of A Given Node in a Binary Tree

Solution

Let’s start with the main idea to solve this problem.

• Find the level of the given node in the binary tree by doing a pre-order traversal on it. 
• When the level is found, print all the nodes present in that level, which is not a sibling of the node or the node itself. 
• The only thing to take care of is, siblings should not be printed. 
• To handle this, we change the printing function to first check for siblings and print nodes only if it is not a sibling. 
   

Now let’s check the implementation in C++

Implementation

#include <iostream>
using namespace std;
 
// Data structure to store a binary tree node
struct Node
{
    int key;
    Node *left, *right;
 
    Node(int key)
    {
        this->key = key;
        this->left = this->right = nullptr;
    }
};
 
// Function to find the level of the given node `x`
void findLevel(Node* root, Node* x, int index, int &level)
{
    // return if the tree is empty or level is already found
    if (root == nullptr || level) {
        return;
    }
 
    // if the given node is found, update its level
    if (root == x) {
        level = index;
    }
 
    // recur for the left and right subtree
    findLevel(root->left, x, index + 1, level);
    findLevel(root->right, x, index + 1, level);
}
 
void printLevel(Node* root, Node* node, int level)
{
    // base case
    if (root == nullptr) {
        return;
    }
 
    // print cousins
    if (level == 1)
    {
        cout << root->key << " ";
        return;
    }
 
    // recur for the left and right subtree if the given node
    // is not a child of the root
    if (!(root->left && root->left == node ||
            root->right && root->right == node))
    {
        printLevel(root->left, node, level - 1);
        printLevel(root->right, node, level - 1);
    }
}
 
// Function to print all cousins of a given node
void printAllCousins(Node* root, Node* node)
{
    int level = 0;
 
    // find the level of the given node
    findLevel(root, node, 1, level);
 
    // print all cousins of a given node using its level number
    printLevel(root, node, level);
}
 
int main()
{ 
    Node* 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);
    printAllCousins(root, root->right->left);
 
    return 0;
}

Output:

Time Complexity:
The time complexity of printing cousins of a given node is O(n), where n is the total number of nodes in the binary tree.

Space Complexity:
This program requires O(h) extra spaces for the recursive call stack, where h is the height of the given binary tree. In the worst case, we can have a skewed tree where h will be equal to the number of nodes in the binary tree. Hence in the worst-case space complexity will be O(n).

Frequently Asked Questions

How do you print cousins in a binary tree?

The idea is to find the level of the given node in the binary tree by doing a preorder traversal on it. Once the level is found, print all nodes present in that level, which is not a sibling of the node or the node itself. 

What is the cousin of a given node?

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise. Two nodes of a binary tree are cousins if they have the same depth with different parents.

How do you print nodes from a binary tree?

You start traversing from the root, then go to the left node, then you again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it as visited and move to the right subtree. Continue the same algorithm until all nodes of the binary tree are visited.

What is a full node in the binary tree?

Full Nodes are nodes that have both left and right children as non-empty.

Conclusion

In this blog, we learned how to find Print Cousins of a given node in a Binary Tree and followed by the implementation in C++. The time complexity to Print Cousins of a given node in a Binary Tree is O(n) and the space complexity is O(h).

If you want to learn about finding more information to print cousins of a given node in a binary tree, we have a separate article that covers the approaches used to solve the problem. Do give it a read.

Recommended Problems:

• Print Nodes At Distance K From Node
• Kth Ancestor Of A Node In Binary Tree
• Segregate Even And Odd Nodes In A Linked List
   

Recommended Reading:

• Check if Two Nodes are Cousins
• Print All Nodes That Are a Distance of K from the Leaf Node
• Print All Root Leaf Paths With Their Relative Positions
• Print All Prime Levels of a Binary Tree
• Print Ancestors of a Given Node
   

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.