Skip to content

Instantly share code, notes, and snippets.

@aaronjwood
Created November 27, 2017 19:47
Show Gist options
  • Save aaronjwood/00c0a6b8e0cd749d30e6bc5f51ca13c6 to your computer and use it in GitHub Desktop.
Save aaronjwood/00c0a6b8e0cd749d30e6bc5f51ca13c6 to your computer and use it in GitHub Desktop.
Lowest common ancestor of a binary tree
class LCA {
static class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
Node root;
Node findLCA(Node root, int n1, int n2) {
if (root == null || root.data == n1 || root.data == n2) {
return root;
}
Node left = findLCA(root.left, n1, n2);
Node right = findLCA(root.right, n1, n2);
return left == null ? right : right == null ? left : root;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment