Preview

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.

  top most

  bottom most

  left most

  right 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

  recursive

  iterative

  tree-like

 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 left-most node

  visit the right-most node

  visit the first found leaf node

  visit the root node

 7. In the following example, what is the root node, left most node, and right most node?
rootleftandrightmost.png

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

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

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

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

 8. In this example, pre-order traversal would:
rootleftandrightmost.png

  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

  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

 9. What travsersal method would be necessary to produce an output of: 0,1,2,3,4,5,6,7,8,9,10?
rootleftandrightmost.png

  pre-order

  post-order

  It is not possible to produce this output using any travsersal method

  in-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

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

  right most node

  root

  left most node

 12. If a '5' is added to this BST, where is it likely to go?
binarysearchtree_question1.png

  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 go directly and immediately to the right of the 0004

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

 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.
binarysearchtree_question2.png

  3

  1

  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
binarysearchtree_question3.png

  deleting a node from a linked list

  traversing a tree using post-order

  the process of updating a stack using two pointers

  inserting a node using pre-order

 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.

  next

  previous

  right

  root

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

  TRUE

  FALSE

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

  TRUE

  FALSE

 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()

  11,5,15,2

  2,5,11,15

  11

  15,11,5,2

 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[0]:
        return False
 
    lastNode[0]=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 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

  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

 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


Report an error