Trees Review

 

Essentially, trees are an abstraction that allow for hierarchical organization of “things”.

These “things” can be anything, but when we’re learning trees they are often numbers (or letters). An abstract data type just means that it is a way of organizing data that we may use later, without care for how the abstraction is actually implemented (for example with lists, or with a class).

Some basic definitions. Let t be this tree:

A node is an entry in a tree (represented by circles). A node has two things associated with it, a value (accessed via t.label or label(t)), and branches, the nodes it points to (accessed via t.branches or branches(t), sometimes called children). The root of a tree is its first node.

An important point: the root of a tree is, in essence, the tree, because it contains all information you could possibly want (the label of the root, the root’s children, the labels of all of the roots children, the root’s children’s children, etc…). As such, each child node of the root is also a tree.

Finally, leaves are just nodes without any children. Some examples for understanding. Write in terms of numbers:

What is the root label (write in code too, done for you)? 1, t.label

What are the branches of the root (in code too)?

What are the labels of the branches of the root (in code too)?

What are the branches of the tree rooted at 2 (in code too, assume branches is implemented as a list of branches)?

How many leaves are there in t?

Is a leaf a tree?

If we removed the node containing 6, how many leaves are there in t? What is the root?

You essentially have all information you might want for studying trees. But it takes a while to get used to messing with trees. Practice problems are usually the best for handling these issues. Two topics that I think are very important to know well when considering trees are list comprehensions and recursion (tree recursion!!)

List comprehensions come up when needing to access branches of a tree and do something (usually a recursive call) branch. In these types of problems, its easiest to consider base cases based off of leaves (really just trees with one node, no branches). Figure out what to do in this case, then figure out how to build a list comprehension so that any tree will simplify to this case.

The thing that seems to be most confusing at first is the difference between doing something on a node and doing something on a label. You’ll have to use both of these interchangeably, so get them down well!

Solutions to questions for understanding

What is the root label (write in code too, done for you)? 1. t.label

What are the branches of the root (in code too)? Tree rooted at 2, tree rooted at 6. t.branches

What are the labels of the branches of the root (in code too)? 2, 6. [a.label for a in t.branches]

What are the branches of the tree rooted at 2? Tree rooted at 11,tree rooted at 2, tree rooted at -4. t.branches[0].branches (depending on the implementation)

How many leaves are there in t? 4

Is a leaf a tree? Yes. It is a tree with no branches.

If we removed the node containing 6, how many leaves are there in t? What is the root? 3, 1.

Other Resources (good practice problems)

(from Katya Stukalova’s 2017 “Linked Lists & Trees”)