Aug 012017
 

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;
}

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)