# 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

static

tertiary

hierarchical

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

a,z

f,k

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)

TRUE

FALSE

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 _____

equal to the left-most leaf node

equal to the root node

1

NULL

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 class that represents a binary tree

A Python function that represents a binary search 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 traversal using two stacks

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

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 right child of 3

4 becomes the left child of 1

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

TRUE

FALSE

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 node is None or node.key > key:

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

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

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 node is None or node.key == key:

if key ==current_node.key: