TREES

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

• 15, 20, 10, 23, 25, 42, 35, 39, 30

• 15, 10, 23, 25, 20, 35, 42, 39, 30

• 10, 20, 15, 23, 25, 35, 42, 39, 30

• 15, 10, 25, 23, 20, 42, 35, 39, 30

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

• 2

• 3

• 4

• 6

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 56. Which of the following sequences CANNOT be the sequence of nodes examined?

• {10, 75, 64, 43, 60, 57, 56}

• {79, 14, 72, 57, 16, 53, 56}

• {90, 12, 68, 34, 62, 45, 56}

• {9, 85, 47, 68, 43, 57, 56}

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I. 81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

• I and III only

• III only

• III and IV only

• II and III only

A binary search tree is generated by inserting in order the following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is

• (4, 7)

• (7, 4)

• (3,8)

• (8,3)

A binary search tree is used to locate the number 43. Which of the following probe sequences is not possible?

• 61 52 14 17 40 43

• 10 65 31 48 37 43

• 2 3 50 40 60 43

• 81 61 52 14 41 43

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ________ .