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...

Persistent Systems Software Engineer interview questions & answers

A Software Engineer was asked 5mo agoQ. What is a virtual function?
A Software Engineer was asked 7mo agoQ. What recommendation systems have you worked on?
A Software Engineer was asked 7mo agoQ. Explain one data structure that you know.

Popular interview questions of Software Engineer

A Software Engineer was asked 5mo agoQ1. What is a virtual function?
A Software Engineer was asked 5mo agoQ2. What is the difference between an Interface and an abstract class?
A Software Engineer was asked 7mo agoQ3. Write a program that prints a star pattern.

Top HR questions asked in Persistent Systems Software Engineer

A Software Engineer was asked 5mo agoQ1. Please introduce yourself.
A Software Engineer was asked 8mo agoQ2. Which technology are you interested in working with?
A Software Engineer was asked 8mo agoQ3. Why this company?
Persistent Systems 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