Tree
- Graph: a graph is, by definition, a collection of nodes (or vertices) and edges connecting these nodes.
- Tree: A tree is defined as a graph without any undirected cycles (i.e., cycles that would come about if we replaced directed edges with undirected edges) nor any unconnected parts.
- two types of tree:
| rooted tree | unrooted tree |
|---|---|
| A given node can have a single parent node above it and can have any number of children nodes below it. (directed) | No notion of parent and children. Instead, a given node has neighbors. (undirected) |
Noted: empty tree can also be considered a rooted binary tree
Four traversal algorithms:
pre-order: VLR (Visit-Left-Right)
- in-order: LVR (Left-Visit-Right)
- post-order: first recurse on the left child (if one exists), then we recurse on the right child (if one exists), and then we visit the current node.
level-order: visit nodes level-by-level
Question: What is the worst-case time complexity of performing a pre-order, in-order, post-order, or level-order traversal on a rooted binary tree with n nodes?
Ans: O(n)