Table of Contents

1. Intro to Trees

tree.png

1.1. Linear structures vs. tree structure

node-parade.png

Lists, Queues, and Stacks are all examples of linear structures. Now we will work with trees, which are hierarchical.

tree-example2.png

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.

tree-terminology.png

  • 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. tree-terminology2.png
  • 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.

    tree-parent.png

  • 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.

    tree-children.png

  • Sibling: Nodes that are children of the same parent node are siblings of each other.

    tree-siblings.png

  • 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.

tree-descendants.png

  • 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.

    tree-subtree.png

  • 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.

tree-height.png

  • Depth of a node \(n\): The length of the path (amount of edges) from that node \(n\) to the root of the tree.

    tree-depth.png

Review 1. Given this tree:

nodes-leaves-tree.png

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:

review-protoindoeuropean.png

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".

  • Identify the children of Persian:
  • Identify the parent of French:
  • Identify the ancestors of Spanish:
  • Identify the descendants of German:

Review 3. Given this tree:

review-heights1.png

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".

  • Identify the height of the tree:
  • The height of the "Help menu" subtree is:
  • The height of the "Play menu" subtree is:
  • The height of the "Exit" subtree is:

3. Types of trees

tree-generic.png

  • 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.

    tree-binary.png

  • 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.

    tree-binarysearchtree.png

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.

    tree-full.png

  • 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.

      tree-complete.png

  • 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.

    tree-balanced.png

4. Binary tree traversals

traversal.png

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

traverse-preorder.png

We begin at the root node. The algorithm here is:

  1. Display current node's value
  2. Traverse to the left subtree
  3. Traverse to the right subtree

4.2. Inorder traversal

traverse-inorder.png

We begin at the root node. The algorithm here is:

  1. Traverse to the left subtree
  2. Display current node's value
  3. Traverse to the right subtree

4.3. Postorder traversal

traverse-postorder.png

We begin at the root node. The algorithm here is:

  1. Traverse to the left subtree
  2. Traverse to the right subtree
  3. Display current node's value

Review 4.

nodes-leaves-tree.png

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.

  • The preorder traversal is:
  • The inorder traversal is:
  • The postorder traversal is:

Author: RachelWil

Created: 2026-10-14 Wed 11:12

Validate