Answer to Question #227079 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

class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
class BinaryTree
{
    Node root;
    BinaryTree(int key)
    {
        root = new Node(key);
    }
 
    BinaryTree()
    {
        root = null;
    }
 
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
 
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
 
        tree.root.left.left = new Node(4);
    }
}