Preview

12 - Binary Trees

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

  Root: 4 Leaf of right subtree: 2

  Root: 11 Leaf of right subtree: 4

  Root: 2 Leaf of right subtree: 4

  Root: 5 Leaf 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. (Note: this is not a binary tree)

  modules / left / right / variable

  nodes / subtree 1 / subtree 2 / variable

  nodes / left / right / data

  variables / branch / child / data

 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? (Note: this is not a binary
uploads/2117498888_HEIGHT_OF_TREE.png

  0

  2

  1

  3

 4. In this example "7" as root has depth ____, "19" has depth ____ and "23" depth ____ (Note: this is not a binary tree)
uploads/1268656170_HEIGHT_OF_TREE.png

  two, one, zero

  two, zero, one

  one, two, zero

  zero, one, two

 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, 5, 1, 7, 2, 12, 8, 4, 3, 11

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

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

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

 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

  1 and 3 are true

  4 - all are true!

  1 and 2 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 binary tree is being created using existing nodes

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

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

  a node is inserted between an existing node and the root

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

  Both are Post-Order examples

  Post-Order / Pre-Order

  Both Pre-order examples

  Pre-order / Post-Order