Binary Search Tree Quiz

Suppose we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequence could not be the sequence of the node examined?

• 2, 252, 401, 398, 330, 344, 397, 363

• 924, 220, 911, 244, 898, 258, 362, 363

• 925, 202, 911, 240, 912, 245, 258, 363

• 2, 399, 387, 219, 266, 382, 381, 278, 363

In full binary search tree every internal node has exactly two children. If there are 100 leaf nodes in the tree, how many internal nodes are there in the tree?

• 25

• 49

• 99

• 101

If a node having two children is to be deleted from binary search tree, it is replaced by its

• In-order predecessor
  
  
  

• In-order successor

• Pre-order predecessor

• Pre-order successor

In a full binary tree, every internal node has exactly two children. A full binary tree with 2n+1 nodes contains

• n leaf node
  
  

• n internal nodes

• n-1 leaf nodes

• n-1 internal node

Which of the following statements about binary trees is NOT true?

• Every binary tree has at least one node.

• Every non-empty tree has exactly one root node.

• Every node has at most two children

• Every non-root node has exactly one parent.

If the two tree traversals are:

1) Inorder: DGBAHEICF

2) postorder: GDBHIEFCA

 

then the preorder tree traversal can be…

• A-B-D-G-C-E-H-I-F

• A-B-G-D-E-C-H-I-F

• B-A-D-G-C-E-H-I-F

• A-B-D-G-C-E-H-F-I

How many distinct binary search trees can be created out of 4 distinct keys?

• 14

• 24

• 5

• 42

We are given a set of n distinct elements and an unlabelled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

• 0

• 1

• n!

• 1/n+1