LCA of Binary Tree Problem Statement

You are given a binary tree consisting of distinct integers and two nodes, X and Y. Your task is to find and return the Lowest Common Ancestor (LCA) of these two nodes.

The LCA of X and Y is defined as the farthest node from the root that is a shared ancestor of both X and Y.

Note:
You can assume that the nodes X and Y exist in the given binary tree.

Example:

Input Format:
The first line contains an integer 'T', the number of test cases to run. For each test case: The subsequent line contains the tree's nodes in level order, with node values separated by spaces. Use -1 to denote null nodes. The second line contains two integers, 'X' and 'Y', representing the nodes for which you need to find the LCA.
Example Tree Representation:

Example Tree

Example input for this tree: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format:
For each test case, output the value of the LCA node of the given two nodes in the binary tree. Print the output on a new line for each test case.

Constraints:

  • 1 <= T <= 100
  • 0 <= N <= 3000, where N is the number of nodes in the binary tree.
  • 0 <= DATA <= 10^4, where DATA is a node value.
  • Time Limit: 1 second
Note:
The explanation provided earlier describes how the input is structured for the tree. In the actual input, the nodes are given in a single line, separated by spaces.
AnswerBot
4d

Find the Lowest Common Ancestor of two nodes in a binary tree.

  • Traverse the binary tree to find the paths from the root to nodes X and Y.

  • Compare the paths to find the last common node, which is the Low...read more

Help your peers!
Add answer anonymously...
Samsung Full Stack Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter