Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution
4.
Implementation
5.
Frequently Asked Questions
5.1.
How do you print cousins in a binary tree?
5.2.
What is the cousin of a given node?
5.3.
How do you print nodes from a binary tree?
5.4.
What is a full node in the binary tree?
6.
Conclusion
Last Updated: Mar 27, 2024

Print Cousins of A Given Node in a Binary Tree

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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

illustration image

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. 
     

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:

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.

Recommended Problems:

Recommended Reading:

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.

Previous article
Check Sum of Covered and Uncovered nodes of Binary Tree
Next article
The Maximum Cost of Splitting Binary Tree into Two Halves
Live masterclass