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);
}
}
Question 4: Create a method for a Binary Search tree that finds the lowest common ancestor...
in C++ Find the least common ancestor (LCA) of two nodes in a “binary search tree.” Please read the key vector {500,300,600,550,700,750,200,150,250,350,800}. Pick up two random keys and show their LCA. note(also write the algorithm in steps. solution should have the screenshots of source code and output, code should be done in dev or codeblock so it can easily run on my computer)
Binary Search Tree Part A: The code attached in this document is a sample code to demonstrate insert operation in binary search tree. Please fill in the missing part for the insert method to make the program work. The expected output should be as follows. 20 30 40 50 60 70 80 Part B: Find Lowest Common Ancestor (LCA) of a Binary Search Tree. According to WikiPedia definition , The lowest common ancestor is defined between two nodes v and...