Created
November 27, 2017 19:47
-
-
Save aaronjwood/00c0a6b8e0cd749d30e6bc5f51ca13c6 to your computer and use it in GitHub Desktop.
Lowest common ancestor of a binary tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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