Check duplicate parenthesis in an expression
June 29, 2017
Medicine tablet (Pill) taking puzzle
August 2, 2017

Check if two node are siblings in a binary tree

Given a binary tree and two values. Find if these values appear in sibling nodes in the tree. For example, if tree is

Then 2 and 6 are siblings but 6 and 9 are not siblings (they are cousin nodes).

Solution

The check for sibling is simple. In recursive traversal of the tree we need to check if the given values are:

  • left and right child of current node.
  • Siblings in the left subtree.
  • Siblings in the right subtree.

If any of the above three conditions are true, then they are siblings , else not.
The terminating condition remains the same as that in the traversal. Below is the code for same:
Code

#include <stdio.h>
#include <stdlib.h>
#define false 0
// Node OF A BINARY TREE
typedef struct node
{
    int data;
    struct node *left;
    struct node *right;
} Node;
// ALLOCATE NEW NODE WITH DATA.
Node* getNode(int v)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = v;
    temp->left = temp->right = NULL;
    return temp;
}
bool isSibling(Node *root, int x, int y)
{
    // TERMINATING CONDITION
    if (root==NULL)
        return 0;
    bool a = false, b = false, c = false;
    if(root->left != NULL && root->right != NULL)
        a = ( (root->left->data == x && root->right->data == y) ||
              (root->left->data == y && root->right->data == x) );
    if(root->left != NULL)
        b = isSibling(root->left, x, y);
    if(root->right != NULL)
        c = isSibling(root->right, x, y);
    return (a || b || c);
}
int main()
{
    Node *root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);
    if(isSibling(root, 5, 6))
        printf("SIBLINGS");
    else
        printf("NOT SIBLINGS");
    return 0;
}

1 Comment

  1. Asif says:

    Your are greate. from pakistan

Leave a Reply

Your email address will not be published. Required fields are marked *