# 02 - Tree Traversal

1. There are three commonly used traversal methods: Pre-order, In-order and ________________

Post-order

Root-order

Observe-order

Last-order

2. In this traversal method, the root node is visited first, then the left subtree and finally the right subtree

Post-order

In-order

Pre-order

Root-order

3. In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. Remember that every node may represent a subtree itself

Pre-order

Post-order

Root-order

In-order

4. In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node

Root-order

Pre-order

Post-order

In-order

5. Post-order traversal of the following binary tree would result in:

d b e a f c g

Post-order traversal cannot be done on this tree

a b d e c f g

d e b f g c a

6. In-order traversal of the following binary tree would result in:

In-order traversal cannot be done on this tree

d b e a f c g

d e b f g c a

a b d e c f g

7. Pre-order traversal of the following binary tree would result in:

d e b f g c a

Pre-order traversal cannot be done on this tree

d b e a f c g

a b d e c f g

8. True or false: In a preorder traversal of a binary search tree, the first item printed out is always the smallest one

False. Reason: The first node printed out in a preorder traversal is the root, which is greater than the nodes in the left subtree.

True. Reason: The first node printed out is always smaller than the nodes in the right and left subtree

True. Reason: The first node is always the smallest or first element to be entered into the tree

False. Reason: The first node printed out in a preorder traversal is always smaller than the nodes in the right subtree.

9. Have a look at the following python implementation of a traversal method. Specifically, the function Xtraversal - what type of traversal is it?
```class Node:

def __init__(self, data):

self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):

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

# WHAT TYPE OF TRAVERSAL IS OCCURING HERE?
# Left ->Right -> Root
def XTraversal(self, root):
res = []
if root:
res = self.XTraversal(root.left)
res = res + self.XTraversal(root.right)
res.append(root.data)
return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)```

Root-order

Pre-order

In-order

Post-order

10. Analyse the following python program that shows in-order implementation. What would replace the ?????s in the code?
```class Node:

def __init__(self, data):

self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):

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

# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
?????????????????????????????????????
return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)```

res.append(left.data)

res = res.append(root.data)

res = res + self.inorderTraversal(root.right)

res = res + self.inorderTraversal(root.left)

11. The following code shows an OOP representation of a Binary tree (Python). The class represents an individual node. Analyse the code and select the statement that is correct
```class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key

# A function to do pre-order tree traversal
def printpreorder(root):

if root:

# First recur on left child
printpreorder(root.left)

# then print the data of node
print(root.val),

# now recur on right child
printpreorder(root.right)

# A function to do inorder tree traversal
def printinorder(root):

if root:

# First recur on left child
printinorder(root.left)

# the recur on right child
printinorder(root.right)

# now print the data of node
print(root.val),

# A function to do Postorder tree traversal
def printPostorder(root):

if root:

# First print the data of node
print(root.val),

# Then recur on left child
printPostorder(root.left)

# Finally recur on right child
printPostorder(root.right)

# Driver code
root = Node(1)
root.left      = Node(2)
root.right     = Node(3)
root.left.left  = Node(4)
root.left.right  = Node(5)
print "Preorder traversal of binary tree is"
printPreorder(root)

print "\nInorder traversal of binary tree is"
printInorder(root)

print "\nPostorder traversal of binary tree is"
printPostorder(root) ```

The comments and names of the functions do not correlate to their function. The first function is correctly commented as pre-order, but the second is post-order and the third function is carrying out in-order tree traversal

The comments and names of the functions do not correlate to their function. The first function is in-order, the second is post-order and the third function is carrying out pre-order tree traversal

The code implementation has three correct functions for traversal but the implementation of the node attributes in the __init__ is incorrect

The code implementation correctly sets up a node with left and right values and three accurate functions for traversal

12. T is a binary tree of height 3. If every internal node of T has 1 child, then there is a total of 8 nodes.

TRUE

FALSE

13. In-order traversal tends to retrieve the data according to its inherent sequence (for example, alphabetically)

TRUE

FALSE

14. What is the time complexity of pre-order traversal in an iterative fashion?
`Hint: Since you have to go through ALL the nodes, the complexity becomes …………………`

O(1)

O(nlogn)

O(logn)

O(n)

15. What is the space complexity of post-order traversal, assuming recursion is used? (d is the tree depth and n is the number of nodes)
`Hint: In the worst case we have d stack frames in the recursive call, hence the complexity is ………………..`

O(nlogd)

O(n)

O(d)

O(1)