LCA in a Binary Search Tree

You are given a binary search tree (BST) containing N nodes. Additionally, you have references to two nodes, P and Q, within this BST.

Your task is to determine the Lowest Common Ancestor (LCA) of these two nodes. The LCA of two nodes P and Q is defined as the lowest node in the BST that has both P and Q as descendants (allowing a node to be a descendant of itself).

Input:

The first line contains an integer 'T', representing the number of test cases.
For each test case: 
- The first line contains two space-separated integers P and Q, indicating the nodes whose LCA needs to be found.
- The second line contains integers representing the BST elements in level order, separated by spaces. If a node does not have a left or right child, it is represented by -1.

Output:

For each test case, print the LCA of nodes P and Q on a separate line.

Example:

Example input for a tree:

1
2 3
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation of the example:

  • Level 1: Root node is 1.
  • Level 2: Left child of 1 is 2 and right child is 3.
  • Level 3: Left child of 2 is 4 (right is -1/null), left of 3 is 5, right is 6.
  • Level 4: Right child of 4 is 7; others are null (-1).
  • The input ends when all nodes at the final level are null (-1).

Constraints:

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 5000
  • 0 ≤ Data ≤ 106 and Data ≠ -1

Note:

The format explained was to clarify how input is generated for a given tree structure. All elements for the tree levels are space-separated in one line.

AnswerBot
4mo

The task is to find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST).

  • Traverse the BST from the root to find the LCA of nodes P and Q.

  • Compare the values of nodes P and Q with...read more

Help your peers!
Select
Add answer anonymously...

Top Software Engineer Interview Questions Asked at Persistent Systems

Q. What is the difference between an Interface and an abstract class?
Q. What is a virtual function?
Q. Write a program that prints a star pattern.
Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

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

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits