Register

BST search

• recategorized by
2,390 views
0 0 votes
Identify the correct sequence for searching 105 in a binary search tree?

a. 500,250,190,220,150,120,105
b. 80,800,500,90,270,280,105
c. 20,30,80,200,90,120,105
d. 30,50,80,200,90,120,105

Plz help me.

1 Answer

Best answer
2 2 votes

Searching in a BST always starts at the root. We compare a data stored at the root with the key we are searching for. If the node

does not contain the key we proceed either to the left or right child depending upon the comparison. If the result of the comparison is

negative we go to the left child, otherwise - to the right child. 

You need to check the following conditions:

(i) The left sub-tree of a node contains only nodes with keys less than the node's key.

(ii) The right sub-tree of a node contains only nodes with keys greater than the node's key.

Options  C and D are correct sequences for 150.

• edited by
Voting & Accepting an answer helps improve the community
← Previous · Merge SortNext → · How many N bits Stri...
← Previous in category · GATE | GATE MOCK 201...Next in category → · binary tree
Position:
Show:

Related questions

6 6 votes
2 2 answers
309
309 views
GO Classes asked Jul 27
309 views
GO Classes DPP | GATE CS, DA | Data Structure | BST Search Path
Suppose numbers between $1$ and $1000$ are stored in a binary search tree. We search for the key $363$.Which of the following sequences could not be the sequence of nodes...
4 4 votes
2 2 answers
220
220 views
GO Classes asked Jul 15
220 views
GO Classes DPP | GATE CS, DA | Data Structure | BST Search
A Binary Search Tree has $15$ nodes. Every node except those at the lowest level has both a left child and a right child.A key is searched in this BST. The key may or may...
4 4 votes
1 1 answer
204
204 views
GO Classes asked Jul 14
204 views
GO Classes DPP | GATE CS, DA | Data Structure | BST Search Complexity
Consider the following statement:“$\text{Searching for an element in a balanced Binary Search Tree with N nodes will require exactly}$ $\mathrm{\log (N)}$ $\text{compare ...
4 4 votes
1 1 answer
177
177 views
GO Classes asked Jul 14
177 views
GO Classes DPP | GATE CS, DA | Data Structure | BST Search
The following strings are inserted into an empty Binary Search Tree in the given order, using normal lexicographic dictionary order:$\text{Paris, London, Rome, Vienna, Du...