[16.1] In the lecture, we discussed how trees are great for storing hierarchical data (data that occurs in connected layers). What are two contexts in which using a Tree may be helpful?
Two contexts in which using a Tree may be helpful are:
File systems in your computer.
Family trees of origin in real life.
[16.2] Consider the following tree with a highlighted node in blue:
What is the value of the blue highlighted node?
What is the green node called (in relation to the blue node)?
What are the pink nodes called (in relation to the blue node)?
What is the green node called (in relation to the entire tree)?
What are the pink nodes called (in relation to the entire tree)?
9
Node 9's parent
Node 9’s children
Root
Leaves
[16.3] Consider the following tree with two highlighted regions:
What do we call the red and blue highlighted regions?
What is the root of the blue highlighted region? What about the red?
What nodes does the rightmost subtree of node 6 contain?
What are the leaf nodes of the above tree?
Subtrees
The blue root is node 2. The red root is node 9
Node 6 and node 1
Leaf nodes are nodes that have no children, and in this tree we have 3, 7, 2 and 1.
[16.4] What condition must binary trees satisfy?
A binary tree is a tree that must satisfy the condition of having at most 2 children per node.
[16.5] Consider that we represent a sports tournament bracket as a tree. What would the root represent? What about the leaves?
In the context of representing a sports tournament bracket as a tree:
The root would represent the team that won the entire tournament.
The leaves would represent all of the teams that competed in this tournament.
[16.6] Which of the following trees is a Binary Search Tree (BST)?
Solution:
The one on the right is not a BST. Notice that it breaks the ordering invariant, there are numbers on the left of 1 that are greater than 1, however, a BST requires that for any parent node, all the nodes on its left must be less than and all its nodes on the right must be greater than the value of the parent node. On the right of the tree, there are two 9s, which is also not allowed in a BST. We cannot have duplicate values.
The one on the left is a valid BST.
[16.7]
Solution:
The root: S
Children of node X: A and R
Parent of node X: T
Leaves: A, R, H
Code Reading & Writing
[16.8] Consider the following code meant to represent a tree:
This function will return a list of the elements of the given tree in left-to-right order, where each element of the list is the original value in the tree squared. In essence, this function traverses the binary tree recursively and constructs a list containing the squares of the values associated with each node.
[16.11] Write a recursive program printValues(T) that recursively prints the values of a given binary tree T.
def printValues(T):
if T["left"] == None and T["right"] == None:
print(T["contents"])
else:
# Recursive print everything to the left of the current node
if T["left"] != None:
printValues(T["left"])
# Print the current node
print(T["contents"])
# Recursive print everything to the right of the current node
if T["right"] != None:
printValues(T["right"])
[16.12] Convert this tree to a Python representation:
[16.13] Write a function called findMax(T) that returns the maximum element of a binary tree passed as a parameter.
def findMax(T):
if T["left"] == None and T["right"] == None:
return T["contents"]
else:
current = T["contents"]
# Recursively find the maximum value to the left of the current node
if T["left"] != None:
leftMax = findMax(T["left"])
# Recursively find the maximum value to the right of the current node
if T["right"] != None:
rightMax = findMax(T["right"])
return max(current, leftMax, rightMax)
[16.14] Write a function findChildren(T, node) which returns a list containing the children of the given node within a given binary tree T.
def findChildren(T, node):
if T == None:
return []
else:
# Check if we have reached the desired node
if T["contents"] == node:
children = []
# Add any existing children to the list
if T["left"] != None:
children.append(T["left"]["contents"])
if T["right"] != None:
children.append(T["right"]["contents"])
return children
else:
# Recursively search for the node to the left and right of the current node
leftChildren = findChildren(T["left"], node)
rightChildren = findChildren(T["right"], node)
return leftChildren + rightChildren
[16.15] Write a function countNodes(t) that takes a tree of values and counts the number of nodes in the given tree.
# Version 1: Base case leaf node
def countNodes(t):
if t["left"] == None and t["right"] == None:
return 1
else:
count = 0
if t["left"] != None:
count += countNodes(t["left"])
if t["right"] != None:
count += countNodes(t["right"])
return count + 1
# ----------
# Version 2: Base case empty tree
def countNodes(t):
if t == None:
return 0
else:
count = 0
count += countNodes(t["left"])
count += countNodes(t["right"])
return count + 1
[16.16] Write a function umNodes(t) that takes a tree of values and adds all the values of the nodes in the tree.
def sumNodes(t):
if t["left"] == None and t["right"] == None:
return t["contents"]
else:
result = 0
if t["left"] != None:
result += sumNodes(t["left"])
if t["right"] != None:
result += sumNodes(t["right"])
return result + t["contents"]
[16.17] Write the function listValues(t), which takes a tree and returns a list of all the values in the tree. The values can be in any order, but try to put them in left-to-right order if possible.
def listValues(t):
if t["left"] == None and t["right"] == None:
return [t["contents"]]
else:
result = []
if t["left"] != None:
result = result + listValues(t["left"])
if t["right"] != None:
result = result + listValues(t["right"])
return result + [t["contents"]]
[16.18] Write a function findBSTMax(t) to find the maximum element in a Binary Search Tree.
