Loading...
Loading...
Loading...
Priya, the class representative, stores her classmates' roll numbers in a binary search tree. She inserts them one by one, in the given order, into an empty tree. A smaller number goes to the left of a node, a larger one to the right.
Then the teacher asks about q roll numbers. Search for each one from the root and count the roll numbers you compare it with. Print FOUND c if it is in the tree, or MISSING c if it is not, where c is that count.
FOUND c or MISSING c.Example 1
Input
7 50 30 70 20 40 60 80 3 40 65 50
Output
FOUND 3 MISSING 3 FOUND 1
40 is compared with 50, 30 and 40. 65 is compared with 50, 70 and 60, and 60 has no right child. 50 is the root itself.
Example 2
Input
4 10 20 30 40 2 40 5
Output
FOUND 4 MISSING 1
Increasing inserts make a chain to the right, so 40 needs 4 comparisons. 5 stops at once: 10 has no left child.
Try the problem first. Open one hint at a time.
To insert x, start at the root and go left when x is smaller, right when it is larger, until you reach an empty spot. Put the new node there.
Searching follows the same path. Count each node you compare with.
The search stops in one of two ways: you find x, or the next child you need is missing.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor