If you need help reviewing Mutable Trees, take a look at these resources:
We will be using the OOP implementation of
Trees from lecture,
Each question has a "Toggle Solution" button -- click it to reveal that question's solution.
Define each of the following terms:
- binary search tree
- entry/datum: an item contained inside of a node
- node: a single "circle" or vertex in a tree that contains an item (the node is the container, the datum is the item inside that container).
- child: a node that has a parent (i.e. a node that branches off from another node)
- parent: a node that has at least one child (i.e. a node that has other nodes branching off from it
- leaf: a node that has no children (has no other nodes branching off underneath it).
- forest: one or more trees
binary search tree: a type of tree that satisfies the following conditions:
- each node can have at most 2 children, called a left and a right
- every element in the subtree to the left of the node must be smaller than the element in the node.
Which of the following are valid
- Tree(5, [Tree(1), Tree(5)])
- Tree(4, [Tree(2)])
- Tree(2, [Tree(2, [4, 5])])
- Invalid: trees must contain at least one element
- Valid: this constructs a leaf with 3 as its entry
- Valid: this constructs a tree whose datum is 5, and has two children whose elements are 1 and 5
- Valid: this is a Tree that has one child
- Invalid: the children of a tree must also be trees
Draw a graphical representation of the following tree and answer these three questions:
Tree(25, [Tree(14, [Tree(9), Tree(20)]), Tree(30, [Tree(27)])])
- What number is contained in the root of this tree?
- Which numbers are contained in leaves?
- How many children does the node containing 14 have?
- 9, 20, 27
- 2 children