Answer to Question #226994 in Java | JSP | JSF for Ayush

Question

There is a binary tree given to you. In which each of the node represents the student in the class.
You are playing a game in which you need to team up with one of student in class. Team can be
formed in such a way that in a team both of the students can’t have same parent in tree and should
be at the same level in binary tree.
Input: we have given you some pair of students you need to find that is the team valid or not.
Output: ‘Yes’ if the team is valid or ‘No’ if the team is invalid.
(a) Optimal solution of O(n) for checking the team validity.
(b) How many tree traversal is required for the solution of the above problem.
Marking Scheme: Total 15 marks-> 10 for part (a)( Algorithm explanation + Pseudo-code +
runtime and data structure used)+ 5 for part (b)(explanation is required)

Answer 1

a)

Algorithm Explanation

The explanation is simple because involves checking if two nodes in the binary tree are cousins.

Two nodes in a binary tree are cousins if they are on the same level and they do not belong to the same parent (not siblings)

Pseudocode Or Code:

package binarytree;
class Node
{
    int student;
    Node leftNode, rightNode;
 
    Node(int data)
    {
        student = data;
        leftNode = rightNode = null;
    }
}
 
class BinaryTree
{
    Node rootNode;
 
    
    boolean isSibling(Node list, Node aNode, Node bNode)
    {
        
        if (list == null)
            return false;
 
        return ((list.leftNode == aNode && list.rightNode == bNode) ||
                (list.leftNode == bNode && list.rightNode == aNode) ||
                isSibling(list.leftNode, aNode, bNode) ||
                isSibling(list.rightNode, aNode, bNode));
    }
 
   
    int level(Node list, Node pointer, int lev)
    {
        
        if (list == null)
            return 0;
 
        if (list == pointer)
            return lev;
 
        
        int l = level(list.leftNode, pointer, lev + 1);
        if (l != 0)
            return l;
 
        
        return level(list.rightNode, pointer, lev + 1);
    }
 
  
    boolean isCousin(Node list, Node aNode, Node bNode)
    {
        
        return ((level(list, aNode, 1) == level(list, bNode, 1)) &&
                (!isSibling(list, aNode, bNode)));
    }
 
   
    public static void main(String args[])
    {
        BinaryTree node = new BinaryTree();
        node.rootNode = new Node(1);
        node.rootNode.leftNode = new Node(2);
        node.rootNode.rightNode = new Node(3);
        node.rootNode.leftNode.leftNode = new Node(4);
        node.rootNode.leftNode.rightNode = new Node(5);
       node.rootNode.leftNode.rightNode.rightNode = new Node(15);
        node.rootNode.rightNode.leftNode = new Node(6);
        node.rootNode.rightNode.rightNode = new Node(7);
        node.rootNode.rightNode.leftNode.rightNode = new Node(8);
 
        Node node1, node2;
        node1 = node.rootNode.leftNode.leftNode;
        node2 = node.rootNode.rightNode.rightNode;
        if (node.isCousin(node.rootNode, node1, node2))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

The time complexity of this algorithm is O(n).

Data structure used is a binary tree as presented above.

b)

At most three binary tree traversals are required for the solution above since left and right subtrees must be traversed in all most all the functions that are contained in the solution.