Preview

05 - Binary Tree Algorithms

 1. Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are________________ data structures. 
The storage of some information is naturally ____________________.

Example: File storage system on a computer

file system
-----------
     /    <-- root
  /      \
...       home
      /          \
   Level 1       Level 2
    /       /      |     \
  ...      cs101  cs112  cs113

  binary

   hierarchical

  static

  tertiary

 2. In this example, the top most node is 'j'. ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. The leaf nodes are: 
     tree
      ----
       j    <-- root
     /   \
    f      k  
  /   \      \
 a     h      z

  f,k

  a,z

  a, h, z

  f,k,a,h,z

 3. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and slower than arrays)

  FALSE

  TRUE

 4. Binary Tree Representation in C: A tree is represented by a pointer to the topmost node in tree. If the tree is empty, then value of root is _____

  1

  NULL

  equal to the root node

  equal to the left-most leaf node

 5. Which statement best describes the following? 
class Node: 
    def __init__(self,key): 
        self.left = None
        self.right = None
        self.val = key

  A Python class that represents an individual node

  A Python function that assigns values to three nodes

  A Python function that represents a binary search tree

  A Python class that represents a binary tree

 6. Analyse the following code implementation. Which statement best describes what it is doing? 
# A binary tree node 
class Node: 
      
    # Constructor to create a new node 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
  
# An iterative function to do postorder traversal of a 
# given binary tree 
def postOrderIterative(root):  
  
    if root is None: 
        return          
      
    # Create two stacks  
    s1 = [] 
    s2 = [] 
      
    # Push root to first stack 
    s1.append(root) 
      
    # Run while first stack is not empty 
    while s1: 
          
        # Pop an item from s1 and append it to s2 
        node = s1.pop() 
        s2.append(node) 
      
        # Push left and right children of removed item to s1 
        if node.left: 
            s1.append(node.left) 
        if node.right: 
            s1.append(node.right) 
  
        # Print all elements of second stack 
    while s2: 
        node = s2.pop() 
        print node.data, 
  
# Driver program to test above function 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
root.right.left = Node(6) 
root.right.right = Node(7) 
postOrderIterative(root)

  Python program for recursive postorder recursive traversal using two stacks and a node constructor

  Python program for iterative postorder traversal using two stacks

  Python program for recursive postorder traversal using a binary search tree and single stack

  Python program for recursive postorder traversal using two stacks

 7. Analyse the following code for a Python implementation of a Binary tree. What happens at the last command? 
# Python program to introduce Binary Tree 
  
# A class that represents an individual node in a 
# Binary Tree 
class Node: 
    def __init__(self,key): 
        self.left = None
        self.right = None
        self.val = key
 
  
# create root 
root = Node(1) 
''' following is the tree after above statement 
        1 
      /   \ 
     None  None'''
  
root.left      = Node(2); 
root.right     = Node(3); 
    
''' 2 and 3 become left and right children of 1 
           1 
         /   \ 
        2      3 
     /    \    /  \ 
   None None None None'''
  
  
root.left.left  = Node(4);

  4 becomes the right child of 2

  4 becomes the left child of 1

  4 becomes the right child of 3

  4 becomes left child of 2

 8. A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level 
               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30

  FALSE

  TRUE

 9. Searching a binary search tree for a specific key can be programmed recursively or iteratively. Fill in the blanks for this recursive version (line 2) 
def search_recursively(key, node):
    #WHAT SHOULD GO HERE?
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    # key > node.key
    return search_recursively(key, node.right)

  if node is None or node.key

  if key is NONE or node.key ==node:

  if node is None or node.key > key:

  if node is None or node.key == key:

 10. What code would go in line 6? (this is an iterative version of searching a binary search tree) 
def search_iteratively(key, node): 
    current_node = node
    while current_node is not None:
        if key == current_node.key:
            return current_node
        #WHAT CODE WOULD GO HERE?
            current_node = current_node.left
        else: # key > current_node.key:
            current_node = current_node.right
    return current_node

  if node is None or node.key == key:

  if key < current_node.key:

  if key ==current_node.key:

  if node is None or node.key > key:


Report an error