Trees Quick Review

Tree = An abstract data type, meaning that it’s not a built in type in python (like an integer or a string)

• Because they are not a built in part of python, we have defined trees in a specific way for the purposes of 61A — this is not how everyone defines trees

Trees have 2 parts:

1. Label = A value, can be any type (integer, string, even a tree if you want!)

2. Branches = Must be a list of trees

Trees are naturally recursive structures because the branches are always a tree, so any function that can be called on the whole tree can be called on a branch of the tree (here’s your smaller subproblem for recursion!)

Some Extra Definitions

Binary Tree = Tree where every node has 0, 1, or 2 branches

Binary Search Tree = Binary tree where any nodes to the left of the label have values less than the label, any nodes of the label have values greater than the label, and all branches are also BSTs