Posted on by Kalkicode
Code Binary Tree

Print cousins of a given node in binary tree in c

C program for Print cousins of a given node in binary tree. Here more information.

// Include header file
#include <stdio.h>
#include <stdlib.h>

/* 
  C Program 
  Print cousins of given node in a binary tree
*/
// Node of Binary Tree
typedef struct TreeNode
{
    // Define useful field of TreeNode
    int data;
    struct TreeNode * left;
    struct TreeNode * right;
}TreeNode;


TreeNode * getTreeNode(int data)
{
    // Create dynamic memory of TreeNode
    TreeNode * me = (TreeNode * ) malloc(sizeof(TreeNode));
    if (me == NULL)
    {
        // Failed to create memory 
        return NULL;
    }
    // Set node value
    me->data = data;
    me->left = NULL;
    me->right = NULL;
    return me;
}
typedef struct BinaryTree
{
    // Define useful field of BinaryTree
    struct TreeNode * root;
    int height;
}BinaryTree;

BinaryTree * getBinaryTree()
{
    // Create dynamic memory of BinaryTree
    BinaryTree * me = (BinaryTree * ) malloc(sizeof(BinaryTree));
    if (me == NULL)
    {
        // Failed to create memory 
        return NULL;
    }
    // Set initial tree root to null
    me->root = NULL;
    me->height = 0;
    return me;
}
// Display Inorder view of binary tree
void inorder(TreeNode * node)
{
    if ((node != NULL))
    {
        // Executing left subtree
        inorder(node->left);
        // Print node value
        printf(" %d ", node->data);
        // Executing right subtree
        inorder(node->right);
    }
}
// Check whether given key node are exist in binary tree or not.
// If key exists then return its parent node and
// calculate the height of key node
TreeNode * nodeHeight(BinaryTree * me, 
    TreeNode * node, int level, int key)
{
    if ((node == NULL))
    {
        // When get empty node
        return NULL;
    }
    else if (((node->left != NULL && node->left->data == key) || 
        (node->right != NULL && node->right->data == key)))
    {
        // When given key exists in binary tree
        // Get node height
        me->height = level + 1;
        // return parent node
        return node;
    }
    else
    {
        // Used to detect key node in left subtree
        TreeNode * result = nodeHeight(me,node->left, level + 1, key);
        if ((result != NULL))
        {
            // If get a parent node of given key
            return result;
        }
        return nodeHeight(me,node->right, level + 1, key);
    }
}
// Print cousin nodes in given level
void findCousinNode(TreeNode * node, 
    int depth, TreeNode * parent, int level)
{
    if ((node == NULL || parent == node || level > depth))
    {
        // When node is null
        // or when root node is parent of key
        // or when level exceed print level
        return;
    }
    if ((depth == level))
    {
        // Display cousin nodes
        printf(" %d ", node->data);
        return;
    }
    // Recursively execute left and right subtree
    findCousinNode(node->left, depth, parent, level + 1);
    findCousinNode(node->right, depth, parent, level + 1);
}
// This are handling the request of
// printing cousin node of given key
void printCousins(BinaryTree * me, int key)
{
    if ((me->root->data == key))
    {
        // There are no cousins of root node
        printf("Cousin nodes of %d is : None ",key);
        return;
    }
    me->height = 0;
    // First get height and parent node of given key
    TreeNode * parent = nodeHeight(me,me->root, 0, key);
    if ((parent != NULL))
    {
        printf("\nCousin nodes of %d is : ",key);
        findCousinNode(me->root, me->height, parent, 0);
        printf("\n");
    }
    else
    {
        printf("Given key node [%d] is not exist",key);
    }
}
int main()
{
    // Make object of Binary Tree
    BinaryTree * tree = getBinaryTree();
    /*
      Construct Binary Tree 
      -----------------------
             1
           /   \
          6     8
         / \   / \
        2   3 7   5
       /           \
      9             11
    */
    // Add nodes
    tree->root = getTreeNode(1);
    tree->root->left = getTreeNode(6);
    tree->root->left->left = getTreeNode(2);
    tree->root->right = getTreeNode(8);
    tree->root->right->right = getTreeNode(5);
    tree->root->right->left = getTreeNode(7);
    tree->root->left->right = getTreeNode(3);
    tree->root->left->left->left = getTreeNode(9);
    tree->root->right->right->right = getTreeNode(11);
    // Display tree elements
    printf("\nBinary Tree Nodes : ");
    inorder(tree->root);
    printf("\n");
    // Test Cases
    printCousins(tree, 2);
    printCousins(tree, 1);
    printCousins(tree, 5);
    printCousins(tree, 4);
    printCousins(tree, 9);
}

Output

Binary Tree Nodes :  9  2  6  3  1  7  8  5  11

Cousin nodes of 2 is :  7  5
Cousin nodes of 1 is : None
Cousin nodes of 5 is :  2  3
Given key node [4] is not exist
Cousin nodes of 9 is :  11

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment