Page 255 - DCAP407_DATA_STRUCTURE

Data Structure

13.4 Self Assessment

1. State whether the following statements are true or false:
(a) A binary search tree has binary nodes.
(b) The efficiency of a binary search tree depends on the height of the tree.
(c) The smallest possible height of a tree with n nodes is log 2n.
(d) In a binary search tree, a node with minimum value is found by traversing and obtaining the
right most node of the tree.
(e) A tree must be balanced to obtain the smallest height, where both the left and right sub-trees
have the same number of nodes.
2. Fill in the blanks:
(a) In searching, the node being search is called as a …………………….

(b) We obtain the number of ……………………. in the tree by traversing the tree and
incrementing the counter whenever a node is visited.
(c) To insert a new element in an existing binary search tree, first we compare the value of the
…………………… node with the current node value.
3. Select a suitable choice for every question:

(a) The maximum level of a tree is referred as the ……………………. of the tree.
(i) Height (ii) Node (iii) Leaf (iv) Root
(b) In searching operation, the node to be searched is known as.
(i) Key node (ii) Head node (iii) Start node (iv) Leaf node
(c) Deletion of a leaf node involves setting left or right pointer of the parent node to?

(i) Zero (ii) NULL (iii) Non zero (iv) One
13.5 Review Questions
1. “Binary search trees have more advantages when compared to other data structures”. Justify.
2. “Performance of a binary search tree depends on its height”. Explain.
3. Write a function that will search a given binary search tree for a specific key.
Answers: Self Assessment

1. (a) True (b) True (c) False (d) False (e) True
2. (a) Key node (b) Nodes (c) New
3. (a) Height (b) Key node (c) NULL
13.6 Further Readings

Lipschutz.S. (2011). Data Structures with C. Delhi: Tata McGraw hill
Reddy.P. (1999). Data Structures Using C. Bangalore:Sri Nandi Publications

http://en.literateprograms.org/Binary_search_tree_(C)

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/binarySearchT
ree.htm

248 LOVELY PROFESSIONAL UNIVERSITY