Question

Question 4:

Create a method for a Binary Search tree that finds the lowest common ancestor of two nodes in a tree (nodesLCA). The two nodes are input by the user identified by their values. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.

Illustrate the performance of the nodesLCA method. Excute the method on following pairs: (500, 271), (21, 203) and (53 , 991)

Answer 1

As in worst case wholse tree have to be traversed only once so not more than that so we can safely say the method will have a time complexity of O(n).

/* Class to represent Node of a tree which contains
 *  left and right child of currents node and key value
 */
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
}


public class BinaryTree {
  // Root of the tree implemented in Node class
  Node root;

  Node findLowestCommonAncestor(int node1, int node2) {
    return findLowestCommonAncestor(root, node1, node2);
  }

  // This function returns pointer to LCA of two given
  // values node1 and node2. This function assumes that node1 and
  // node2 are present in Binary Tree
  Node findLowestCommonAncestor(Node node, int node1, int node2) {
    /*
     * Base case condition ie. if The root itself is null then no point in checking further
     */
    if (node == null)
      return null;

    /*
     * If either node1 or node2 matches with root's key, report the presence by returning root (Note
     * that if a key is ancestor of other, then the ancestor key becomes LCA
     */
    if (node.data == node1 || node.data == node2)
      return node;

    // Look for keys in left and right subtrees
    Node left_lca = findLowestCommonAncestor(node.left, node1, node2);
    Node right_lca = findLowestCommonAncestor(node.right, node1, node2);

    /*
     * If both of the above calls return Non-NULL, then one key is present in once subtree and other
     * is present in other, So this node is the LCA
     */

    if (left_lca != null && right_lca != null)
      return node;

    // else check if left subtree or right subtree is LCA
    return (left_lca != null) ? left_lca : right_lca;
  }

   /* 
   * Main class to test LCA functions 
   */
   public static void main(String args[]) {
     BinaryTree tree = new BinaryTree();
     tree.root = new Node(1);//root node
     tree.root.left = new Node(500);//left child of root node
     tree.root.right = new Node(271);//right child of root node
     tree.root.left.left = new Node(21);//left child of left child of root node
     tree.root.left.right = new Node(203);//right child of left child of root node
     tree.root.right.left = new Node(553);//left leaf node
     tree.root.right.right = new Node(991);//right leaf node
     System.out.println("LCA(500, 271) = " + tree.findLowestCommonAncestor(500, 271).data);
     System.out.println("LCA(21, 203) = " + tree.findLowestCommonAncestor(21, 203).data);
     System.out.println("LCA(53 , 991) = " + tree.findLowestCommonAncestor(53 , 991).data);
     System.out.println("LCA(1, 991) = " + tree.findLowestCommonAncestor(1, 991).data);
   }
}