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

Question

Two monkeys Charlie and Leo are standing at two different nodes of a tree.
This tree is very weird, its root is situated at the highest point and grows in a downward
direction.
Also it consists of several nodes and branches connecting two different nodes.But at max 2
branches can originate from a node.
Now ,there are some tasks which they have to perform using some algorithms.Since they are
very lazy they want you to complete those tasks.
Task 1:- They want to move to the root node.So they want to calculate the individual distance
each of them have to travel in reaching to the root.
Task2:-They want to meet with each other .So they want to compute the distance between each
other before they start moving.
Can you help them in achieving these tasks?
Assumption:- Assume Tree as binary Tree.
You will be given the root Node of the tree and the reference nodes containing the address of
the nodes where charlie and leo are present
Task1 and Task2 -(Algorithm Explanation+Pseudo code+Time Complexity)

Answer 1

Task 1

Algorithm:

The algorithm to perform this task is very simple and it involves counting the number of edges from a given node to the root node. In this, we consider Charlie's node and Leo's node.

Pseudo-code or Code:

package task1;


import java.util.*;
public class Task1 {


static class Node
{
    int item;
    Node leftNode, rightNode;
}
 


static Node new_node(int data)
{
    Node tempNode = new Node();
    tempNode.item = data;
    tempNode.leftNode = null;
    tempNode.rightNode = null;
    return tempNode;
}
 
//Can be used to get the distance between any  nodes and the root
//This function can be used to get the distance between Charlie and the root
//Also the function can be applied to get the distance between Leo and the root
static int findingDistance(Node first, int x)
{
    
    if (first == null)
    return -1;
 
    
    int dist = -1;
 
    
    if ((first.item == x) ||
        (dist = findingDistance(first.leftNode, x)) >= 0 ||
        (dist = findingDistance(first.rightNode, x)) >= 0)
        return dist + 1;
 
    return dist;
}
 


public static void main(String[] args)
{
    Node node = new_node(5);
    node.leftNode = new_node(10);
    node.rightNode = new_node(15);
    node.leftNode.leftNode = new_node(20);
    node.leftNode.rightNode = new_node(25);
    node.leftNode.rightNode.rightNode = new_node(45);
    node.rightNode.leftNode = new_node(30);
    node.rightNode.rightNode = new_node(35);
 
    System.out.println(findingDistance(node, 45));
}
}

The Time Complexity is O(n) since there is only one traversal.

Task 2:

Algorithm Explanation
Distance(x1, x2) = Distance(root, x1) + Distance(root, x2) - 2*Distance(root, lca) 
'x1' and 'x2' are keys that the distance between them is to be found
Distance(x1, x2) is the distance between the nodes

lca is the lowest common ancestor of x1 and x2

Pseudocode

package task2;




public class Task2 {


   public static class Node {
        int data;
        Node leftNode;
        Node rightNode;
 
        public Node(int data) {
            this.data = data;
        }
    }
 
    public static Node LCA(Node rootNode, int x1, int x2)
    {
        if (rootNode == null)
            return rootNode;
        if (rootNode.data == x1 || rootNode.data == x2)
            return rootNode;
 
        Node left = LCA(rootNode.leftNode, x1, x2);
        Node right = LCA(rootNode.rightNode, x1, x2);
 
        if (left != null && right != null)
            return rootNode;
          if (left == null && right == null)
              return null;
        if (left != null)
            return LCA(rootNode.leftNode, x1, x2);
        else
            return LCA(rootNode.rightNode, x1, x2);
    }
 
 
    public static int findingLevel(Node rootNode, int i, int l)
    {
        if (rootNode == null)
            return -1;
        if (rootNode.data == i)
            return l;
        int left = findingLevel(rootNode.leftNode, i, l + 1);
        if (left == -1)
            return findingLevel(rootNode.rightNode, i, l + 1);
        return left;
    }
 
    public static int findingDistance(Node rootNode, int x, int y)
    {
        Node lca = LCA(rootNode, x, y);
 
        int d1 = findingLevel(lca, x, 0);
        int d2 = findingLevel(lca, y, 0);
 
        return d1 + d2;
    }
     
    // Testing program
    public static void main(String[] args) {
         
        
        Node root = new Node(1);
        root.leftNode = new Node(2);
        root.rightNode = new Node(3);
        root.leftNode.leftNode = new Node(4);
        root.leftNode.rightNode = new Node(5);
        root.rightNode.leftNode = new Node(6);
        root.rightNode.rightNode = new Node(7);
        root.rightNode.leftNode.rightNode = new Node(8);
        System.out.println("Dist(4, 5) = "
                             + findingDistance(root, 4, 5));
                              
        
 
    }
}
 

Time Complexity of Task 2 is also O(n) since there is only one traversal of the list