Learning Objectives
- Explore structure and use of a binary tree
- Practice building programs by applying small functions to solve more complex problems
Submission Instructions
Using the Prairielearn workspace, test and save your solution to the following exercises. (You are welcome to download and work on the files locally but they must be re-uploaded or copied over to the workspace for submission).
You will only need to modify the following files:
lab_trees.ipynb
Assignment Description
In this lab we’ll review tree traversals on binary trees and write some useful functions using both traversals and recursion.
In-Order Traversal
# INPUT:
# node, a treeNode object storing the root of a binaryTree
# OUTPUT:
# A list containing the in-order traversal of the binaryTree
# Note: The traversal should return a list NOT print them to terminal like the in-class examples
def inOrder(node):
In class we covered pre-order traversal using print statements. Here you must write an in-order traversal that does not print each value in order and instead returns a single list containing all values in order. This is slightly harder than the problem covered in class but still follows the broad strokes of our previous implementations.
Recall that in-order traversal works as follows: For each node in the tree, everything to the left of the node will be listed before the node, and everything to the right of the node will be listed after that node.
Post-Order Traversal
# INPUT:
# node, a treeNode object storing the root of a binaryTree
# OUTPUT:
# A list containing the post-order traversal of the binaryTree
# Note: The traversal should return a list NOT print them to terminal like the in-class examples
def postOrder(node):
You must also write postOrder traversal with the same structure.
Recall that poster-order traversal works as follows: For each node in the tree, everything to the left of the node will be listed, followed by everything to the right of the node. Only after recursing to all children will we then list the node itself.
areEqual
# INPUT:
# root1, a treeNode object storing the root of a binaryTree
# root2, a treeNode object storing the root of a binaryTree
# OUTPUT:
# A boolean value (True) the two trees have identical structure
# and (False) otherwise
def areEqual(root1, root2):
Checking to see if two trees are identical is a useful function for all trees not just binary trees. There are two ways to solve this – you can go through an elaborate recursive exercise where you check each node by parallel moving through two trees simultaneously. Or you can use the above traversal functions to explore the shape of your tree. But be careful – you can’t just use one traversal to solve this problem. Take the following two trees for example. They have very different structure but have the same inOrder traversal!
HINT: One traversal producing an identical result does not prove that two trees are identical. But two traversals will identify a unique tree!
*TREE 1*
7
/ \_
5 6
/ \ / \
1 2 3 4
*TREE 2*
______________________________ 4
______________________________/
______________ 6
______________/
______ 3
______/
__ 7
__/
2
/
5
/
1
pathToNode()
# INPUT:
# root, a treeNode object storing the root of a binaryTree
# val, the value of the node we are looking for
# OUTPUT:
# A list of node values from root to the node of interest
# If the node does not exist, return an empty list
def pathToNode(root, val):
If you need to know if a specific value exists in a tree, a traversal is a great way to find it. But if I need to remember my exact path, it becomes a slightly trickier recursive problem. Here, modify your traversal code to return the path to a particular value (or return an empty list if the value does not exist).
distBetweenNodes()
# INPUT:
# root, a treeNode object storing the root of a binaryTree
# v1, the value of one node we are looking for
# v2, the value of the other node we are looking for
# OUTPUT:
# An integer storing the distance between two nodes in our tree
# The number should be the number of edges between the two nodes
# ignoring the direction of edges.
def distBetweenNodes(root, v1, v2):
Another useful metric in all trees (not just a binary tree) is the distance between nodes. To find this value, you have find the common parent between two nodes at the furthest depth [this is known as the ‘lowest (or least) common ancestor’]. Given this shared path to a shared parent, the distance is then the sum of the distance that each node is from this common ancestor. Consider carefully if this needs to be a recursion problem at all given your previous functions!