Answer to Question #230347 in Java | JSP | JSF for Anonymous

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 algorithm involves checking if there are nodes that are in the same level but they are not siblings. This means that determining if two nodes are cousins.

Code

//Checking if two nodes are cousins. 
package studentteam;
class ListNode
{
    int item;
    ListNode left_node, right_node;
 
    ListNode(int student)
    {
        item = student;
        left_node = right_node = null;
    }
}
 
public class StudentTeam
{
    ListNode root_node;
 
    //Method that checks if nodes are siblings
    boolean is_sibling(ListNode root, ListNode a_node, ListNode b_node)
    {
        
        if (root == null)
            return false;
 
        return ((root.left_node == a_node && root.right_node == b_node) ||
                (root.left_node == b_node && root.right_node== a_node) ||
                is_sibling(root.left_node, a_node, b_node) ||
                is_sibling(root.right_node, a_node, b_node));
    }
 
   
    int levelOfNode(ListNode root, ListNode node, int level)
    {
        
        if (root == null)
            return 0;
 
        if (root == node)
            return level;
 
        
        int l = levelOfNode(root.left_node, node, level + 1);
        if (l != 0)
            return l;
 
        
        return levelOfNode(root.right_node, node, level + 1);
    }
  //The core part 
    boolean isCousin(ListNode root, ListNode a_node, ListNode b_node)
    {
        
        return ((levelOfNode(root, a_node, 1) == levelOfNode(root, b_node, 1)) &&
                (!is_sibling(root, a_node, b_node)));
    }
 
   
    public static void main(String args[])
    {
        StudentTeam root = new StudentTeam();
        root.root_node= new ListNode(1);
        root.root_node.left_node = new ListNode(2);
        root.root_node.right_node = new ListNode(3);
        root.root_node.left_node.left_node = new ListNode(4);
        root.root_node.left_node.right_node= new ListNode(5);
       root.root_node.left_node.right_node.right_node = new ListNode(15);
        root.root_node.right_node.left_node = new ListNode(6);
        root.root_node.right_node.right_node = new ListNode(7);
        root.root_node.right_node.left_node.right_node = new ListNode(8);
 
        ListNode node_root1, node_root2;
        node_root1 = root.root_node.left_node.left_node;
        node_root2 = root.root_node.right_node.right_node;
        if (root.isCousin(root.root_node, node_root1, node_root2))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

The above algorithm has a running time of O(n)

Data structure used in the algorithm is a Linked List.

b)

There are three traversal required for the algorithm.

This is because there will be traversal of both the left and the right subtrees.

Additionally, the algorithm involves determining the level of nodes and checking if they are nodes belonging to the same parent.