Background
In one of the previous posts we saw how to find LCA of two nodes in a Binary search tree. In this post we will repeat the same question but now it's just a binary tree not a BST.
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public static BTreeNode findLCA(BTreeNode root, int n1, int n2) { if (root == null ) { return null ; } if (root.getData() == n1 || root.getData() == n2) { return root; } BTreeNode leftNode = findLCA(root.getLeft(), n1, n2); BTreeNode rightNode = findLCA(root.getRight(), n1, n2); if (leftNode != null && rightNode != null ) { return root; } return leftNode != null ? leftNode : rightNode; } |
I have posted complete solution with test cases on my GIT repo of interview question. You can find the code -
Logic is as follows -
- If one of the two nodes is the root, then the root itself is the common ancestor.
- If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
- If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
- Otherwise, root is the Lowest common ancestor.
No comments:
Post a Comment