LCA of binary tree
lowest common ancestor:
method 1)last common node in the paths from the root node to the given nodes will be the lca
For Example: consider the above-given tree and nodes 4 and 5.
Path from root to node 4: [1, 2, 4]
Path from root to node 5: [1, 2, 5].
The last common node is 2 which will be the LCA.
Algorithm:
Find the path from the root node to node n1 and store it in a vector or array.
Find the path from the root node to node n2 and store it in another vector or array.
Traverse both paths untill the values in arrays are same. Return the common element just before the mismatch.
c++:
// C++ Program for Lowest Common Ancestor // in a Binary Tree #include <iostream> #include <vector> using namespace std; // A Binary Tree node struct Node { int key; struct Node *left, *right; }; // Utility function creates a new binary tree // node with given key Node* newNode(int k) { Node* temp = new Node; temp->key = k; temp->left = temp->right = NULL; return temp; } // Function to find the path from root node to // given root of the tree, Stores the path in a // vector path[], returns true if path exists // otherwise false bool findPath(Node* root, vector<int>& path, int k) { // base case if (root == NULL) return false; // Store this node in path vector. // The node will be removed if // not in path from root to k path.push_back(root->key); // See if the k is same as root's key if (root->key == k) return true; // Check if k is found in left or right sub-tree if ((root->left && findPath(root->left, path, k)) || (root->right && findPath(root->right, path, k))) return true; // If not present in subtree rooted with root, // remove root from path[] and return false path.pop_back(); return false; } // Function to return LCA if node n1, n2 are // present in the given binary tree, otherwise // return -1 int findLCA(Node* root, int n1, int n2) { // to store paths to n1 and n2 from the root vector<int> path1, path2; // Find paths from root to n1 and root to n1. // If either n1 or n2 is not present, return -1 if (!findPath(root, path1, n1) || !findPath(root, path2, n2)) return -1; // Compare the paths to get the first // different value int i; for (i = 0; i < path1.size() && i < path2.size(); i++) if (path1[i] != path2[i]) break; return path1[i - 1]; } // Driver Code int main() { // Let us create the Binary Tree // as shown in the above diagram Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); cout << "LCA(4, 5) = " << findLCA(root, 4, 5); cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6); cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4); cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4); return 0; }
java:
// Java Program for Lowest Common Ancestor
// in a Binary Tree
import java.util.ArrayList;
import java.util.List;
// A Binary Tree node
class Node {
int data;
Node left, right;
Node(int value)
{
data = value;
left = right = null;
}
}
public class FindLCA {
Node root;
private List<Integer> path1 = new ArrayList<>();
private List<Integer> path2 = new ArrayList<>();
// Finds the path from root node to given root of the tree
int findLCA(int n1, int n2)
{
path1.clear();
path2.clear();
return findLCAInternal(root, n1, n2);
}
private int findLCAInternal(Node root, int n1, int n2)
{
if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
System.out.println((path1.size() > 0) ?
"n1 is present" : "n1 is missing");
System.out.println((path2.size() > 0) ?
"n2 is present" : "n2 is missing");
return -1;
}
int i;
for (i = 0; i < path1.size() && i < path2.size(); i++) {
if (!path1.get(i).equals(path2.get(i)))
break;
}
return path1.get(i - 1);
}
// Finds the path from root node to given
// root of the tree, Stores the path in a
// vector path[], returns true if path
// exists otherwise false
private boolean findPath(Node root, int n,
List<Integer> path)
{
// base case
if (root == null) {
return false;
}
// Store this node. The node will be removed if
// not in path from root to n.
path.add(root.data);
if (root.data == n) {
return true;
}
if (root.left != null && findPath(root.left, n, path)) {
return true;
}
if (root.right != null && findPath(root.right, n, path)) {
return true;
}
// If not present in subtree rooted with root,
// remove root from path[] and return false
path.remove(path.size() - 1);
return false;
}
// Driver code
public static void main(String[] args)
{
FindLCA tree = new FindLCA();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5): " + tree.findLCA(4, 5));
System.out.println("LCA(4, 6): " + tree.findLCA(4, 6));
System.out.println("LCA(3, 4): " + tree.findLCA(3, 4));
System.out.println("LCA(2, 4): " + tree.findLCA(2, 4));
}
}
output:
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2
Analysis: The time complexity of the above solution is O(N) where N is the number of nodes in the given Tree and the above solution also takes O(N) extra space.
Method 2: The method 1 finds LCA in O(N) time but requires three tree traversals plus extra spaces for path arrays. If we assume that the keys are present in Binary Tree, we can find LCA using single traversal of Binary Tree and without extra storage for path arrays.
The idea is to traverse the tree starting from the root node. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn't match with any of the keys, we recur for left and right subtrees. The node which has one key present in its left subtree and the other key present in the right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise, LCA lies in the right subtree.
c++:
// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that
// n1 and n2 are present in Binary Tree
struct Node* findLCA(struct Node* root, int n1, int n2)
{
// Base case
if (root == NULL)
return NULL;
// If either n1 or n2 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 (root->key == n1 || root->key == n2)
return root;
// Look for keys in left and right subtrees
Node* left_lca = findLCA(root->left, n1, n2);
Node* right_lca = findLCA(root->right, n1, n2);
// If both of the above calls return Non-NULL,
// then one key is present in one subtree and
// other is present in other,
// So this node is the LCA
if (left_lca && right_lca)
return root;
// Otherwise check if left subtree or
// right subtree is LCA
return (left_lca != NULL) ? left_lca : right_lca;
}java:
Node findLCA(Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;
// If either n1 or n2 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 == n1 || node.data == n2)
return node;
// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);
// 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;
// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}
No comments