Preview

12 - Binary Trees

 1. In the following example, what is the a) root node and b) the 'child' node of the right subtree?
uploads/NK4q6.png

  Root: 11 Child of right subtree: 4

  Root: 4 Child of right subtree: 2

  Root: 2 Child of right subtree: 4

  Root: 5 Child of right subtree: 11

 2. A binary tree is made of _____, where each node contains a "_____" reference, a "_____" reference, and a ____ element. The topmost node in the tree is called the root.

  nodes / left / right / data

  nodes / subtree 1 / subtree 2 / variable

  variables / branch / child / data

  modules / left / right / variable

 3. The depth of a node is the number of edges from the root to the node. The height of a node is the number of edges from the node to the deepest leaf. The height of a tree is a height of the root. What is the height of this tree?
uploads/2117498888_HEIGHT_OF_TREE.png

  0

  1

  2

  3

 4. In this example "7" as root has depth ____, "19" has depth ____ and "23" depth ____
uploads/1268656170_HEIGHT_OF_TREE.png

  two, one, zero

  zero, one, two

  one, two, zero

  two, zero, one

 5. Consider the following tree and pre-order traversal. What would be output?
uploads/travsersals.jpg

  8, 5, 4, 9, 7, 11, 1, 12, 3, 2

  8, 5, 9, 7, 1, 12, 2, 4, 11, 3

  9, 5, 1, 7, 2, 12, 8, 4, 3, 11

  9, 1, 2, 12, 7, 5, 3, 11, 4, 8

 6. What would the correct output be for post-order traversal of this tree?
uploads/492294301_travsersals.jpg

  9, 1, 2, 12, 7, 5, 3, 11, 4, 8

  9, 5, 1, 7, 2, 12, 8, 4, 3, 11

  9, 2, 1, 7, 12, 5, 3, 11, 4, 8

  9, 5, 7, 1, 2, 12, 8, 4, 3, 11

 7. Which of the following is true of Binary Search trees?
1. each node contains one key (also known as data)
2. the keys in the left subtree are less 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;
duplicate keys are not allowed.
4. All of the above are true

  4 - all are true!

  1 and 2 are True

  1 and 3 are true

  Only 1 is true

 8. If the node to delete has only one child the procedure of deletion is identical to deleting a node from a linked list - we just bypass that node being deleted. True or False? (refer to image)
uploads/todelete.jpg

  False

  True

 9. What is happening in this python coded implementation of a binary tree?
class BinaryTree():

    def __init__(self,rootid):
      self.left = None
      self.right = None
      self.rootid = rootid

    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

    def insertRight(self,newNode):
        if self.right == None:
            self.right = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.right = self.right
            self.right = tree

    def insertLeft(self,newNode):
        if self.left == None:
            self.left = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.left = self.left
            self.left = tree


def printTree(tree):
        if tree != None:
            printTree(tree.getLeftChild())
            print(tree.getNodeValue())
            printTree(tree.getRightChild())


# test tree

def testTree():
    myTree = BinaryTree("Maud")
    myTree.insertLeft("Bob")
    myTree.insertRight("Tony")
    myTree.insertRight("Steven")
    printTree(myTree)

  a node is inserted between an existing node and the root

  a node is being inserted between the two left and right most nodes.

  a binary tree is being created using only a left sub tree

  a binary tree is being created using existing nodes

 10. Fill in the blanks for the traversal methods below. One example (in-order) has been done for you.
uploads/preorder_inorder.png

  Post-Order / Pre-Order

  Both Pre-order examples

  Pre-order / Post-Order

  Both are Post-Order examples