# 09 - Binary Search Trees

1. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The ________ node in the tree is called the root.

right most

top most

bottom most

left most

2. Binary trees are particularly useful where data is being added on a regular basis and needs to be organised into a logical structure so that it can be searched. That is, where the data is dynamic

TRUE

FALSE

3. Binary trees can be used to hold an ordered set of data. In an ordered binary tree all items to the left of the root will have a smaller key than those on the right of the root. This applies equally to all the _________

leaf nodes that also happen to be parent nodes

numeric values in each node

subtrees

strings associated with each node

4. To insert data into an ordered tree the following ____________ algorithm can be used.
```PROCEDURE insert(Tree, Item)
IF Tree is empty THEN create new tree with Item as the root.
ELSE      IF Item < Root
THEN insert(Left sub-tree of Tree, Item)
ELSE insert(Right sub-tree of Tree, Item)
ENDIF
ENDIF
ENDPROC```

suboptimal

tree-like

iterative

recursive

5. Another common use of a binary tree is to hold an algebraic expression, for example: X + Y * 2

TRUE

FALSE

6. Read the excerpt below about pre-order and fill in the blanks for no.1. In pre-order, what happens first?
```The name pre-order comes from the use of binary trees to
store expressions.

The pre-order traversal produces the operators before the items.

Pre-order is defined as:

1.__________________________?

2. traverse the left sub-tree

3. traverse the right sub-tree.```

visit the right-most node

visit the first found leaf node

visit the root node

visit the left-most node

7. In the following example, what is the root node, left most node, and right most node? Root node: 7; Left most node: 4; Right most node: 10

Root node: 7; Left most node: 0; Right most node: 10

Root node: 7; Left most node: 8; Right most node: 6

Root node: 0; Left most node: 4; Right most node: 6

8. In this example, pre-order traversal would: begin at the root '7' and end at the right most node '10'

begin at the left most node and end at the right most node

begin and end at the root node, visiting the other nodes in between

begin at the left most node and end with the root node

9. What travsersal method would be necessary to produce an output of: 0,1,2,3,4,5,6,7,8,9,10? It is not possible to produce this output using any travsersal method

in-order

pre-order

post-order

10. Can you spot the mistake in the following excerpt about a Binary SEARCH tree?
```A BST is a binary tree where nodes are ordered in the following way:

1 - each node contains one key (also known as data)
2 - the keys in the left subtree are greater then the key in its parent node, in short L > P;
3 - the keys in the right subtree are greater the key in its parent node, in short P < R;
4 - duplicate keys are not allowed.```

Point 2 has a mistake. It should be: the keys in the left subtree are less then the key in its parent node, in short L < P

Both Point 1 and Point 4 are incorrect.

Point 3 has a mistake. It should be that the keys are less than the key in its parent node, in short R < P

There is no mistake. The excerpt is entirely accurate

11. Searching in a BST always starts at the ____ We compare a data stored at the _____ with the key we are searching for

right most node

left most node

last node (e.g. the right most leaf node)

root

12. If a '5' is added to this BST, where is it likely to go? It would go immediately to the left of the 0008

It would replace the 0006 and therefore be immediately to the left of the 0011

It would cause an error, because there is no space for a '5' in this sequence of tree

It would go directly and immediately to the right of the 0004

13. In the following example, if we wanted to delete the '8', follow the method mentioned below and predict what the new 'root' node will be.
```Deletion strategy is as follows:
================================

>>replace the node being deleted with the largest node
in the left subtree and then delete that largest node.

>>By symmetry, the node being deleted can be swapped
with the smallest node in the right subtree.``` 1

3

9

5

14. If the node to be deleted has only one child the procedure of deletion is identical to _____________________- just bypass the node being deleted
`Image source: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html` deleting a node from a linked list

inserting a node using pre-order

traversing a tree using post-order

the process of updating a stack using two pointers

15. Another way of stating the rule that defines a Binary Search Tree is as follows: Fill in the blanks
```The left node always contain values that come before
the ______ node and the right node always contains values
that come after the _____ node.```

previous

right

next

root

16. In a BST that holds words, as might be in an unsorted dictionary, the order is always random.

FALSE

TRUE

17. If the letter 'F' was added to this BST, it would be placed immediately to the left of the letter 'E' FALSE

TRUE

18. In the following Python (class based) representation of a Binary tree, what is the output?
```class Node:

def __init__(self, data):

self.left = None
self.right = None
self.data = data

def insert(self, data):
# Compare the new value with the parent node
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data

# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()

# Use the insert method to add nodes
root = Node(11)
root.insert(5)
root.insert(15)
root.insert(2)

root.PrintTree()```

2,5,11,15

15,11,5,2

11,5,15,2

11

19. A very common interview question is: Given a binary tree, check whether or not it is a binary search tree. Explain the basis of this coded solution.
```def isBST2(tree, lastNode=[NEG_INFINITY]):
if tree is None:
return True

if not isBST2(tree.left, lastNode):
return False

if tree.val < lastNode:
return False

lastNode=tree.val

return isBST2(tree.right, lastNode)

Code source: http://www.ardendertat.com/2011/10/10/programming-interview-questions-7-binary-search-tree-check/```

If a tree is a binary search tree, then traversing the tree pre-order should lead to a sorted order of values in the tree

If a tree is a binary search tree, then traversing the tree post-order should lead to a random order of values in the tree

If a tree is a binary search tree, then each left-most node should be geater in value than the right-most node

If a tree is a binary search tree, then traversing the tree in-order should lead to sorted order of the values in the tree

20. What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?

O(2n) for all

O(Logn) for search, and O(n) for insert and delete

O(1) for all

O(n) for all