print cousin nodes of a given binary tree

Print cousins of a given node in Binary Tree



Given a binary tree and a node, print all cousins of given node. Note that siblings should not be printed.
Example:

Input : root of below tree 
             1
           /   \
          2     3
        /   \  /  \
       4    5  6   7
       and pointer to a node say 5.
Output : 6, 7



The idea to first find level of given node using the approach discussed here. Once we have found level, we can print all nodes at a given level using the approach discussed here. The only thing to take care of is, sibling should not be printed. To handle this, we change the printing function to first check for sibling and print node only if it is not sibling.
Below is C++ implementation of above idea.

// C program to print cousins of a node
#include <stdio.h>
#include <stdlib.h>

// A Binary Tree Node
struct Node
{
    int data;
    Node *left, *right;
};

// A utility function to create a new Binary
// Tree Node
Node *newNode(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

/* It returns level of the node if it is present
   in tree, otherwise returns 0.*/
int getLevel(Node *root, Node *node, int level)
{
    // base cases
    if (root == NULL)
        return 0;
    if (root == node)
        return level;

    // If node is present in left subtree
    int downlevel = getLevel(root->left, node, level+1);
    if (downlevel != 0)
        return downlevel;

    // If node is not present in left subtree
    return getLevel(root->right, node, level+1);
}

/* Print nodes at a given level such that sibling of
   node is not printed if it exists  */
void printGivenLevel(Node* root, Node *node, int level)
{
    // Base cases
    if (root == NULL || level < 2)
        return;

    // If current node is parent of a node with
    // given level
    if (level == 2)
    {
        if (root->left == node || root->right == node)
            return;
        if (root->left)
           printf("%d ", root->left->data);
        if (root->right)
           printf("%d ", root->right->data);
    }

    // Recur for left and right subtrees
    else if (level > 2)
    {
        printGivenLevel(root->left, node, level-1);
        printGivenLevel(root->right, node, level-1);
    }
}

// This function prints cousins of a given node
void printCousins(Node *root, Node *node)
{
    // Get level of given node
    int level = getLevel(root, node, 1);

    // Print nodes of given level.
    printGivenLevel(root, node, level);
}

// Driver Program to test above functions
int main()
{
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(15);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);

    printCousins(root, root->left->right);

    return 0;
}


Output :

6 7


Time Complexity : O(n)
Can we solve this problem using single traversal? Please write your approach in comments.
This article is contributed byShivam Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s