CS61B 2019 Lecture 23 Tree and Graph Traversals

[poanc]

Summary

• Tree Recap
• Trees and Traversals
• Level Order Traversal
• Range Finding
• Graphs
  • Graph Problems
• Depth First Search (Depth First Traversal)
  • Depth First Path Demo
• Tree vs Graph Traversals

Tree Recap

What is a tree?

What is a rooted tree?

What are trees useful for?

Trees and Traversals

Now how do you iterate over a tree? What's the correct 'order'?
Before we answer that question, we must not use the word iteration. Instead, we'll call it 'traversing through a tree' or a 'tree traversal'. Why? No real reason, except that everyone calls iteration through trees 'traversals'. Maybe it's because the world likes alliterations.

So what are some natural ways to 'traverse' through a tree? As it turns out, there are a few –– unlike a list which basically has one natural way to iterate through it:

1. Level order traversal.
2. Depth-First traversals –– of which there are three: pre-order, in-order and post-order.

Pre-order Traversal

Visit a node, then traverse its child : D B A C F E G

preOrder(BSTNode x) {
    if (x == null) return;
    print(x.key)
    preOrder(x.left)
    preOrder(x.right)
}

In-order Traversal

Traverse left child, visit, then traverse right child: A B C D E F G

inOrder(BSTNode x) {
    if (x == null) return;    
    inOrder(x.left)
    print(x.key)
    inOrder(x.right)
}

An alternative way to think about this is as follows:
First, we're at D. We know we'll print out the items from left, then D, then items from right.
[items from left] D [items from right].
Now what's [items from left] equal to? We'll start at B, print out left, then print B, then print stuff from right of B.
[items from left] = [items from B's left] B [items from B's right] = A B C.
A B C D [stuff from right] = A B C D E F G.

Post-order Traversal

Traverse left, traverse right, then visit : A C B E G F D

postOrder(BSTNode x) {
    if (x == null) return;    
    postOrder(x.left)
    postOrder(x.right)
    print(x.key)   
}

[items from left] [items from right] D.
What's [items from left]? It's the output from the B subtree.
If we're at B, we'd get [items from left of B] [items from right of B] B, which is equal to A C B.
Following this through, we get: A C B E G F D

What good are all these traverse

Level Order Traversal

Range Finding

Graphs

What is a graph?

That's it! No other restrictions.
In general, note that all trees are also graphs, but not all graphs are trees.

Simple Graphs only

Graphs can be divided into two categories: simple graphs and multigraphs

The graph in the middle has 2 distinct edges going from/to bottom-next to/from bottom-left node. In other words, there are multiple edges between two nodes. This is not a simple graph, and we ignore their existence unless specified otherwise. Graphs like these are called multigraphs.

Look at the third graph. It has a loop! An edge from a node to itself! We don't allow this either. Graphs like these are sometimes categorized as multigraphs, and sometimes, even multigraphs explicitly ban self-loops.

More categorizations.

There are undirected graphs, where an edge (u, v) can mean that the edge goes from the nodes u to v and from the nodes v to u too. There are directed graphs, where the edge (u, v) means that the edge starts at u, and goes to v (and the vice versa is not true, unless the edge (v, u) also exists.) Edges in directed graphs have an arrow.

There are also acyclic graphs. These are graphs that don't have any cycles. And then there are cyclic graphs, i.e., there exists a way to start at a node, follow some unique edges, and return back to the same node you started from.

In the above picture, we can clearly see the difference between how we draw directed and undirected edges.

Take a look at the cyclic graphs. If you start at a, you can run back around using only distinct edges and get back to a. Thus, the graph is cyclic.

Take a look at the top-left graph. Is there any node n, such that if you start at n, you can follow some distinct edges, and get back to n? Nope! (Remember than for directed edges, you must follow the directions. You can go from a to b but not b to a.)

More definitions

Example

Graph Problems

There are many questions we can ask about a graph.

What's cool and also weird about graph problems is that it's very hard to tell which problems are very hard, and which ones aren't all that hard.

For example, consider the Euler Tour and the Hamilton Tour problems. The former... is a solved problem. It was solved as early as 1873. The solution runs in O(E) where E is the number of edges in the graph.

The latter? If you were to solve it efficiently today, you would win every Math award there was, become one of the most famous computer scientists, win a million dollars, etc. No one has been able to solve this efficiently. The best known algorithms run in exponential times. People have been working on it for many decades!

Depth First Traversal

Given a source vertex s and a target vertex t, is there a path between s and t?

In other words, write a function connected(s, t) that takes in two vertices and returns whether there exists a path between the two.

In other words, write a function connected(s, t) that takes in two vertices and returns whether there exists a path between the two.

To begin, let's guess that we have the following code:

if (s == t):
    return true;

for child in neighbors(s):
    if isconnected(child, t):
        return true;

return false;

We start with connected(0, 7)? That recursively calls connected(1, 7), which then recursively calls connected(0, 7). Uh-oh. Infinite looping has occurred.

Alright, let's try a "remember what we visited" approach.

mark s  // i.e., remember that you visited s already
if (s == t):
    return true;

for child in unmarked_neighbors(s): // if a neighbor is marked, ignore!
    if isconnected(child, t):
        return true;

return false;

You may not have realized it, but we just developed a depth-first traversal (like pre-order, post-order, in-order) but for graphs. What did we do? Well, we marked ourself. Then we visited our first child. Then our first child marked itself, and visited its children. Then our first child's first child marked itself, and visited its children.

You may not have realized it, but we just developed a depth-first traversal (like pre-order, post-order, in-order) but for graphs. What did we do? Well, we marked ourself. Then we visited our first child. Then our first child marked itself, and visited its children. Then our first child's first child marked itself, and visited its children.

Depth First Path Demo

link

Tree vs Graph Traversals

Summary