Table of Contents
1. Intro to Trees
1.1. Linear structures vs. tree structure
Lists, Queues, and Stacks are all examples of linear structures. Now we will work with trees, which are hierarchical.
A tree structure could be used to model a filesystem, moves or progress in a game, a family tree. And with a binary search tree, you could store any kind of data and keep it organized as each new item is inserted.
2. Basic terminology
A tree is a type of graph that is completely connected and has no cycles. A tree is made up of nodes/vertices and edges.
- Node: A node is a point in a tree; in the code, it will be a structure that contains data.
- Edge: An edge is a line that connects two nodes; in the code, it will be the pointer from one node to another.
- Root: Each tree will have exactly one root, which all other nodes
branch out from. When drawing a tree, we will generally make it the
top-most node. The root is the only node that has no parent, and every
other node has exactly one parent.

- Leaf: A leaf is a node with no children.
Parent: In a tree, each node has exactly one parent, except for the root node, which has no parent. The parent of node \(n\) is the node directly "above" \(n\), on the path back towards the root.
Child: A node in a tree can have any amount of children. A child of node \(n\) are the nodes directly under \(n\), branching off from it.
Sibling: Nodes that are children of the same parent node are siblings of each other.
- Ancestors: The ancestor of node \(n\) is any node between \(n\) and the root (including the root).
- Descendants: The descendants of node \(n\) is any node derived from node \(n\), going all the way down to the leaves.
Subtree: The subtree of node \(n\) is a tree with node \(n\) as the root, derived from an original tree that contains \(n\). Each node in a tree is essentially the root of its own subtree.
- Height of a node \(n\): The height of some node \(n\) is the amount of edges on the longest path from that node \(n\) to any descendant leaf.
- Height of a tree: The height of a tree is the number of edges on the longest path from the root to a leaf.
Depth of a node \(n\): The length of the path (amount of edges) from that node \(n\) to the root of the tree.
Review 1. Given this tree:
Figure 1: A tree with "A" at the top. A's left node is B, A's right node is C. B's left node is D, B's right node is E. C's left node is F, C's right node is G.
Identify the Leaf and Root nodes.
Review 2. Given this tree:
Figure 2: A tree with "Proto-indo-european" as the root. Proto-indo-european's three children are: "Indo-Iranian", "Latin", and "Germanic". Indo-Iranian's children are: "Sanskrit" and "Persian". Latin's children are: "French" and "Spanish". Germanic's children are: "Norse" and "West Germanic". Sanskrit's child is "Hindi". Persian's children are "Farsi" and "Kurdish". West Germanic's children are "Dutch", "German", and "Yiddish".
Review 3. Given this tree:
Figure 3: A tree that has "Main menu" at the very top. Branching from Main Menu beneath it are "Play menu", "Help menu", and "Exit". Branching from "Play menu" are "Load game", and "New game". Branching from "Load game" is "Level select". Branching from "Help menu" is "Credits".
3. Types of trees
- General tree: A general tree contains a root and subtrees that branch off from that root. There are no restrictions on the way it must be filled, or how many children each node can have.
- n-ary tree: An n-ary tree is a type of tree where each node can have no more than \(n\) children.
A tree where each node can have no more than 2 children. This means a node can have 0, 1, or 2 children.
Binary search tree: A binary seach tree is a binary tree that is sorted. For any given node, its left child has a lesser value, and its right child has a greater value.
3.1. Tree fullness, completeness, and balance
Full binary tree: A full binary tree is one where every node either has 0 children or 2 children.
- Complete binary tree: A complete binary tree is one where all nodes have
2 children, except possibly in the lowest level. Additionally:
- In the 2nd-to-lowest level, if a node has children, then all its siblings to its left must have 2 children each.
- If a node in the 2nd-to-lowest level has only one node, it must be a left child.
This mean the tree fills from left-to-right.
Balanced binary tree: A binary tree is height balanced when, for each node of the tree, each node's left subtree and right subtree differ in height by no more than 1 level.
4. Binary tree traversals
When working with a list, it's easy to just output all the contents from beginning-to-end and call it a day - simple! But how do you output the contents of a binary tree?
4.1. Preorder traversal
We begin at the root node. The algorithm here is:
- Display current node's value
- Traverse to the left subtree
- Traverse to the right subtree
4.2. Inorder traversal
We begin at the root node. The algorithm here is:
- Traverse to the left subtree
- Display current node's value
- Traverse to the right subtree
4.3. Postorder traversal
We begin at the root node. The algorithm here is:
- Traverse to the left subtree
- Traverse to the right subtree
- Display current node's value
Review 4.
Figure 4: A tree with "A" at the top. A's left node is B, A's right node is C. B's left node is D, B's right node is E. C's left node is F, C's right node is G.