Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Problem Statement

Given a binary tree, print all the cousins of a given node. The two nodes are cousins of each other if only if they have different parents, but they have the same level.

For example, consider this

Here 6,7 are cousins of nodes 4 or 5/ 4,5 are cousins of nodes 6 or 7.

Recommended: Try the Problem yourself before moving on to the solution.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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.

#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:

4 5

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.