CSC148 Trees Exam Study Guide
Questions with Complete solutions (A
Graded)
descendants of a value - ANSWER - it children,
its children's children
ancestors of a value - ANSWER - its parent, its parent's parent
Path - ANSWER a sequence of values (nodes_ where there is an edge between each pair of n-
n(i+1)
Length of path - ANSWER the number of edges in a path
- there's a unique path from the root of the tree to each node in that tree
No cycles - ANSWER -There are no cycles
Leaf - ANSWER - a value(node) with no children(no subtrees)
- internal node: a value (node) with one or more children
- Height of a tree: the longest path from the root to one of the leaves (count the number of
values on the path, can be expressed as 1+ the maximum path length in a tree, a
value(node)'s height is 1+ the maximum path length of the tree rotted at that node
, Internal Node - ANSWER A value with one or more children
Height of the tree - ANSWER Longest path from the root to one of the leaves
depth of the value (node) - ANSWER length of the path from the root to that value
arity, branching factor - ANSWER maximum number of children for any node
General Tree Deletion - ANSWER - Hidden Assumption: subtree of a Tree is not empty
def _delete_root(self) -> None:
"""Delete the root of this tree.
Precondition: this tree is non-empty.
"""
if self._subtrees == []:
# This is a leaf. Deleting the root gives an empty
tree. self._root = None
else:
# This tree has more than one value!
# Can't just set self._root = None, need to REPLACE it.
# Strategy 1: "Promote" a subtree.
# 1. Remove the rightmost subtree.
last_subtree = self._subtrees.pop()
# 2. Update self._root
self._root = last_subtree._root
# 3. Update self._subtrees
Questions with Complete solutions (A
Graded)
descendants of a value - ANSWER - it children,
its children's children
ancestors of a value - ANSWER - its parent, its parent's parent
Path - ANSWER a sequence of values (nodes_ where there is an edge between each pair of n-
n(i+1)
Length of path - ANSWER the number of edges in a path
- there's a unique path from the root of the tree to each node in that tree
No cycles - ANSWER -There are no cycles
Leaf - ANSWER - a value(node) with no children(no subtrees)
- internal node: a value (node) with one or more children
- Height of a tree: the longest path from the root to one of the leaves (count the number of
values on the path, can be expressed as 1+ the maximum path length in a tree, a
value(node)'s height is 1+ the maximum path length of the tree rotted at that node
, Internal Node - ANSWER A value with one or more children
Height of the tree - ANSWER Longest path from the root to one of the leaves
depth of the value (node) - ANSWER length of the path from the root to that value
arity, branching factor - ANSWER maximum number of children for any node
General Tree Deletion - ANSWER - Hidden Assumption: subtree of a Tree is not empty
def _delete_root(self) -> None:
"""Delete the root of this tree.
Precondition: this tree is non-empty.
"""
if self._subtrees == []:
# This is a leaf. Deleting the root gives an empty
tree. self._root = None
else:
# This tree has more than one value!
# Can't just set self._root = None, need to REPLACE it.
# Strategy 1: "Promote" a subtree.
# 1. Remove the rightmost subtree.
last_subtree = self._subtrees.pop()
# 2. Update self._root
self._root = last_subtree._root
# 3. Update self._subtrees
