Instructions

User Manual:

Open the PDF directly: View PDF .
Page Count: 2

Download
Open PDF In Browser	View PDF

Binary Search Tree :
Lowest Common
Ancestor
You are given pointer to the root of the binary search tree and two values
the lowest common ancestor (LCA) of
and
in the binary search tree.

In the diagram above, the lowest common ancestor of the nodes
lowest node which has nodes and as descendants.

and

and

. You need to return

is the node

. Node

is the

Function Description
Complete the function lca in the editor below. It should return a pointer to the lowest common ancestor
node of the two values given.
lca has the following parameters:
- root: a pointer to the root node of a binary search tree
- v1: a node.data value
- v2: a node.data value
Input Format
The first line contains an integer, , the number of nodes in the tree.
The second line contains space-separated integers representing
The third line contains two space-separated integers,

and

values.

.

To use the test data, you will have to create the binary search tree yourself. Here on the platform, the
tree will be created for you.
Constraints

The tree will contain nodes with data equal to

and

.

Output Format
Return the a pointer to the node that is the lowest common ancestor of
Sample Input

and

.

and

.

Sample Output
[reference to node 4]
Explanation
LCA of

and

is , the root in this case.

Return a pointer to the node.



---

Source Exif Data:

File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.4
Linearized                      : No
Title                           : 
Creator                         : wkhtmltopdf 0.12.3
Producer                        : Qt 4.8.7
Create Date                     : 2018:06:25 20:54:14Z
Page Count                      : 2
Page Mode                       : UseOutlines

EXIF Metadata provided by EXIF.tools