Preview

02 - Tree Traversal

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

  Post-order

  Observe-order

  Last-order

  Root-order

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

  Post-order

  Pre-order

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

  In-order

  Root-order

  Pre-order

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

  In-order

  Root-order

  Pre-order

  Post-order

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

  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:
post_order_traversal_1.png

  a b d e c f g

  d e b f g c a

  In-order traversal cannot be done on this tree

  d b e a f c g

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

  Pre-order traversal cannot be done on this tree

  d e b f g c a

  a b d e c f g

  d b e a f c g

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

  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 the root, which is greater than the nodes in the left subtree.

  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)

  In-order

  Pre-order

  Root-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 = res.append(root.data)

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

  res.append(left.data)

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

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

  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

 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.

  FALSE

  TRUE

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

  FALSE

  TRUE

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

  O(n)

  O(1)

  O(nlogn)

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

   O(d)

  O(n)

  O(nlogd)


Report an error