Medium Data Structures Trees & Binary Trees
How do you find the Lowest Common Ancestor (LCA) in a binary tree?
Answer
For a general binary tree, use recursion: if current node is null or matches either target, return it. Recursively find LCA in left and right subtrees. If both return non-null, current node is LCA. If only one returns non-null, return that. Time complexity is O(n). For BST, leverage ordering: if both targets are smaller, go left; if both larger, go right; otherwise current node is LCA with O(h) time.
IIT Certified
Master These Concepts with IIT Certification
175+ hours of industry projects. Get placed at Bosch, Tata Motors, L&T and 500+ companies.
Relevant for Roles
Software Engineer Backend Developer Algorithm Developer