All Tracks Data Structures Trees Binary Search Tree Problem

Monk and Cursed Tree
Tag(s):

Binary Search Tree, Data Structures, Easy-Medium

Problem
Editorial
Analytics

Monk has an array $$A$$ having $$N$$ distinct integers and a Binary Search Tree which is initially empty. He inserts all the elements of the array from index $$1$$ to $$N$$ in the BST in the order given in the array. But wait! The tree so formed turns out to be cursed. Monk is having some weird experiences since he made that tree.

So, now to stop all that, Monk has two options, to destroy the BST or to pray to God and ask for a solution. Now since Monk has to use this BST in a Code Monk Challenge, he cannot destroy it. So he prays to God.

God answer his prayers and sends an angel named Micro. Now, Micro asks Monk to find something. He tells him two values, $$X$$ and $$Y$$, present in the BST and ask him to find the maximum value that lie in the path between node having value $$X$$ and node having value $$Y$$. (including $$X$$ and $$Y$$ ).

Now since, Monk is very afraid of that tree he asks for your help.

Input:
First line consists of a single integer denoting $$N$$.
Second line consists of $$N$$ space separated integers denoting the array $$A$$.
Third line consists of two space separated integers denoting $$X$$ and $$Y$$.

Output:
Print the maximum value that lie in the path from node having value $$X$$ and node having value $$Y$$ in a new line.

Constraints:
$$1 \le N \le 10^5$$
$$1 \le A[i] \le 10^9$$
It is ensured that values $$X$$ and $$Y$$ are present in the array.

SAMPLE INPUT
5
4 7 8 6 3
3 7

SAMPLE OUTPUT
7
Explanation

Binary Search Tree for the given array is given below

enter image description here

Path between node having value $$3$$ and node having value $$7$$ is $$3$$ -> $$4$$ -> $$7$$. Maximum value that lies on this path is $$7$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Trees)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications