Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Question

Accepted Answer

To find the least common ancestor (LCA) of two nodes in a binary tree, use a recursive approach to traverse the tree.

1. Start from the root node and check if the current node is null.
2. If the current node matches either of the target nodes, return it.
3. Recursively search for the target nodes in the left and right subtrees.
4. If both left and right subtree calls return non-null values, the current node is the LCA.
5. If only one side returns a non-null value, propagate that value up the tree.

Accepted Answer

You'll find the answer on gfg or leetcode pretty straight forward question.

Asked in IBM and 18 others

Interview Questions from Popular Companies