12 - Binary Trees

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

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

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)

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?

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?

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)

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.

Both are Post-Order examples

Post-Order / Pre-Order

Both Pre-order examples

Pre-order / Post-Order