---
tags: fall 2018 cs61b
---
# Introduction to Trees
[TOC]
## Introduction
Trees are recursively defined data structures and can be visualized as the structure below.

**Definitions:**
* **Nodes:** make up the tree. It is a term is used to describe the structures that hold a value and a connection to other nodes.
* **Root:** the node at the top of the tree (the parent node of all other nodes)
* **Children:** nodes connected to the same parent node; Example: The nodes containing 2 and 7 are children of the node containing 1
* **Leaf:** a node with no children; Example: the node containing 9

In general, trees do not have to retain any certain order or have a limited number of children. Since they are recursive structures, a tree is made up of subtrees. (i.e. In the structure above, the 3 and its children is also considered to be a tree).

### Binary Trees and Binary Search Trees
When a tree is limited to at most 2 children, it is referred to as a **binary tree**. If you want your binary tree to sort its nodes by some order, then we get a **binary search tree** **(BST)**.

The tree below is an example of a BST. In BSTs, the values in the *left children* of a node are *smaller* than the node's value and the values of the right children of a node are *bigger* than the node's value.


### Insertion Into a BST
For BSTs, we usually insert items at leaves (nodes without children).
* If the item being inserted is **smaller** than the leaf, we assign it to be its **left child**.
* If the item being inserted is **greater** than the leaf, we assign it to be its **right child**.
* In CS61B, we usually do not account for duplicate nodes.

### BST Performance
When we analyze the runtime of operations on trees, we analyze it terms of the number of nodes $N$. Therefore, when we analyze performance, we assume there is large number of nodes.

BSTs are great for searching and insertion. However, they can have a few drawbacks performance-wise (i.e. spindly trees).

**Spindly trees** are BSTs with only right children or only left children. Searching for an item or adding a node can possibly mean iterating through all possible nodes.

**Example of spindly tree:**

Therefore, the **worst case runtime** for inserting a node and searching for a node in a BST is $\Theta(N)$.

**What about the best-case runtime?** In the best scenario, the BST is perfectly balanced on both sides. Therefore, it would only take $\Theta(\textrm{log } N)$ to insert or search for a node.

## Tree Traversals
Tree traversals describe when nodes in a binary tree are processed (one way of processing a node would be printing its value).

### Level-Order/Breadth-First Traversal
**Purpose:** Visit nodes by level and process them, from top to bottom and left to right. Given the tree below, we could visit each node level by level and obtain the result below.

**Result:** 1 2 7 5 9 3 4

### Depth-First Traversal
**Purpose:** Visit deeper nodes first (before shallow nodes).

There are three types of depth-first traversal: preorder, inorder, and postorder.

**PreOrder**
* Visit a node and then traverse its children.
* Usually in the order of **root, left, right**.

**Quick way of traversing nodes in PreOrder:**
1. Draw out the tree.
2. Draw a **left peg** for each node.
3. Draw a line around the entire tree structure.
4. Start from the root and follow the line left. Mark the node as visited when the the node's peg passes through the line.


**Result:** 1 2 5 9 7 3 4

**InOrder**
* Traverse left child, visit root, then traverse right child.
* Usually in the order of **left root right**.

**Quick way of traversing nodes in InOrder:**
Follow the same steps as the method for preorder, but assign **downward** pegs to each node.

**Result:** 5 2 9 1 7 4 3

**PostOrder**
* Traverse left, traverse right, then visit.
* Usually in the order of **left right root**.

**Quick way of traversing nodes in PostOrder:**


**The result:** 5 9 2 4 3 7 1

### Difference between Search and Traversal
You also may have learned about **breadth first search** and **depth first search** and related them to **level order/breadth-first traversal** and **depth first traversal** respectively. Preorder, inorder, and postorder traversals all fit into the category of depth first search.

To summarize, **breadth first search** processes nodes in the same order as **level order/breadth-first traversal** and **depth first search** processes nodes in the same order as **depth-first traversal**.

While they do act in a similar way to their counterpart, **searches** mean that you look through the tree for an arbitrary node. **Traversals** mean that you visit every node in a binary tree.