Data Structures and Algorithms for CL 3

Assignment 4

Deadline: Dec, 02 2022 14:00 CET

Exercises

4.1 Calculate the depth of a Node object

Get the depth of a Node object with respect to self (the root). You may use == to test for equality between Node objects. This means that two Node objects with the same data and the same children will not necessarily be equal.

As long as we can run the tests without modification, you may add default parameters to the method if you find it useful.

Return the depth of the Node object if it is found. If the node is not in the subtree whose root is self, return None.

4.2 Complete get_span method

get_span() Returns the span of the Node self as a string.

By “span”, we mean the data of all of the descendant leaves of a node. Write it from left to right and separated by a single whitespace. For example, given the tree below, the span of VP should be slept quite peacefully.

full tree

4.3 Get a Qtree representation of a binary tree

Qtree is a LaTeX package that is very useful for drawing trees. Write a Qtree representation of self and its descendants. If a Node with descendants has depth greater or equal to 3, use a roof for everything below it unless its children are leaves. You can make use of the helper methods make_roof and is_leaf that are provided.

You can find the Qtree documentation under this URL. You only need to understand sections 3.1, 3.2 and 3.3. For testing purposes, please always write the label after both the left and the right square bracket of the node as explained in section 3.2.

You can visualize your tree using LaTeX. You may add default parameters to the signature if you find it useful and it does not require modifying the tests in any way.

An example is shown below:

expected output

Note: We are including two test files which are exactly the same: one uses pytest, while the other one contains the same tests as unittests in case you have trouble running pytest.

Wrapping up

Do not forget to