How to find the least common ancestor for given 2 nodes in a tree?
devquora
Posted On: Dec 24, 2020
The simple O(n) algorithm to find the Least Common Ancestor of n1 and n2 is as follows.
- Calculate the path from the root to n1 and store it in a vector or array.
- Calculate the path from the root to n2 and store it in another vector or array.
- Traverse both paths till the values in arrays are the same. Return the common element just before the mismatch which one is the least common ancestor of given two nodes in a tree.
Related Questions
Subscribe Our NewsLetter
Never Miss an Articles from us.
Recent Articles
Featured Categories
- Common Interview Questions
- Python Flask Interview Questions
- NoSQL Interview Questions
- jQuery Interview Questions
- C Programming Interview Questions
- AngularJs Interview Questions
- Node JS Interview Questions
- JavaScript Interview Questions
- Core Java Interview Questions
- HTML Interview Questions
- Laravel Interview Questions
- Wordpress Interview Questions
- PHP Interview Questions
Amazon Support Engineer Interview Questions
Explain What is STP?
The STP also stands for Spanning Tree Protocol constructs a loop-free logical topography for Ethernet networks. It is a ..
Amazon Support Engineer Interview Questions
Write a function to check if a number is prime?
A prime number is a whole number greater than 1, which is only divisible by 1 and itself. // function check whether a number // is prime or not bool isPrime(int n) { // Corner case if (n...
Amazon Support Engineer Interview Questions
Write a regular expression to validate phone number in XXX-XXX-XXXX format?
A regular expression to validate phone number in XXX-XXX-XXXX format is follows: /^(?:\(\d{3}\)|\d{3}-)\d{3}-\d{4}$/...