Section 7 Chapter 42 - Trees

Connected, undirected graph with no cycles

A tree where one vertex has been designated as the root

Contains the data and are connected together via edges

Connects two nodes

The only node with no parent. All other nodes are descendants of the root

node A is a child of node B is they have a direct connection and node B is closer to the root than node A.

Node A is a parent of node B if they are directly connected and node A is closer to the root

The set of nodes and edges comprised of a parent and its descendants

A node that has no children

A rooted tree where each node has at most two children

A binary tree that holds the items in such a way that a binary search can be conducted on the tree very easily

The first item is placed at the root. When a new item is added visit the root, which becomes the current node. At each current node, if the item is less than the value of the node take the branch to the left, otherwise take the branch to the right. Repeat until you attempt to take a branch that does not exist. Add the item as a node in this place

Pre-order In-order Post-order

The prefix of each traversals refers to how whether, at each subtree, you consider the parent node first, second or third.

Pre-order - producing prefix notation In-order - binary search Post-order - produce reverse polish notation