Scribd
Upload
3 views309 pages

Tree Algorithm Slides

The document provides an overview of trees in graph theory, defining a tree as a connected, undirected graph with no cycles and discussing various applications such as file systems, social hierarchies, and game theory. It also covers different storage representations for trees, including edge lists, adjacency lists, and adjacency matrices, along with the concept of rooted trees and binary search trees. The document concludes with a preview of upcoming content on beginner tree algorithms.

Uploaded by

pumasemj
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views309 pages

Tree Algorithm Slides

The document provides an overview of trees in graph theory, defining a tree as a connected, undirected graph with no cycles and discussing various applications such as file systems, social hierarchies, and game theory. It also covers different storage representations for trees, including edge lists, adjacency lists, and adjacency matrices, along with the concept of rooted trees and binary search trees. The document concludes with a preview of upcoming content on beginner tree algorithms.

Uploaded by

pumasemj
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Graph Theory

Video Series
Storage and
representation
of trees
Definitions and storage representation

William Fiset
Trees!
What is a tree?
Trees!
What is a tree?

tree tree tree not a tree


Trees!
A tree is a connected, undirected graph
with no cycles.

tree tree tree not a tree


Trees!
Equivalently, a tree it is a connected graph
with N nodes and N-1 edges.

4 nodes 6 nodes 13 nodes 7 nodes


3 edges 5 edges 12 edges 8 edges
Trees out in the wild
Trees out in the wild
Filesystem structures are inherently trees

directory

directory directory

directory directory
Trees out in the wild
Social hierarchies
Trees out in the wild
Abstract syntax trees to decompose source
code and mathematical expressions for easy
evaluation.
((x + 6) * -3) > (2 - y)

>

* -

+ -3 2 y

x 6
Trees out in the wild
Every webpage is a tree as an HTML
DOM structure

<html>

<head> <body>

<title> <h1> <ul>

title header <li> <li>

item 1 item 2
Trees out in the wild
The decision outcomes in game theory are often
modeled as trees for ease of representation.

P1

De
es

fe
nf

ct
Co

P2 P2
s

s
De

De
es

es
fe

fe
nf

nf
ct

ct
Co

Co

Tree of the prisoner’s dilemma


Trees out in the wild
There are many many more applications…

• Family trees
• File parsing/HTML/JSON/Syntax trees
• Many data structures use/are trees:
• AVL trees, B-tree, red-black trees,
segment trees, fenwick trees, treaps,
suffix trees, tree maps/sets, etc…
• Game theory decision trees
• Organizational structures
• Probabilty trees
• Taxonomies
• etc…
Storing undirected trees
Storing undirected trees
Start by labelling the tree
nodes from [0, n)

2 3 4 5

6 7 8

9
Storing undirected trees
edge list storage
representation:
0 [(0, 1),
(1, 4),
1 (4, 5),
(4, 8),
2 3 4 5 (1, 3),
(3, 7),
6 7 8 (3, 6),
(2, 3),
9 (6, 9)]

pro: super fast and easy to iterate over.


Storing undirected trees
edge list storage
representation:
0 [(0, 1),
(1, 4),
1 (4, 5),
(4, 8),
2 3 4 5 (1, 3),
(3, 7),
6 7 8 (3, 6),
(2, 3),
9 (6, 9)]
con: storing a tree as a list lacks the
structure to efficiently query all the
neighbors of a node.
Storing undirected trees
adjacency list
representation
0
0 -> [1]
1 -> [0,3,4]
1
2 -> [3]
3 -> [1,2,6,7]
2 3 4 5
4 -> [1,5,8]
5 -> [4]
6 7 8 6 -> [3,9]
7 -> [3]
9 8 -> [4]
9 -> [6]
Storing undirected trees
adjacency list
representation
0
0 -> [1]
1 -> [0,3,4]
1
2 -> [3]
3 -> [1,2,6,7]
2 3 4 5
4 -> [1,5,8]
5 -> [4]
6 7 8 6 -> [3,9]
7 -> [3]
9 8 -> [4]
9 -> [6]
Storing undirected trees
adjacency matrix
representation
0 1 2 3 4 5 6 7 8 9
0 0 0 1 0 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 0 0 0
1 2 0 0 0 1 0 0 0 0 0 0
3 0 1 1 0 0 0 1 1 0 0
2 3 4 5 4 0 1 0 0 0 1 0 0 1 0
5 0 0 0 0 1 0 0 0 0 0
6 7 8 6 0 0 0 1 0 0 0 0 0 1
7 0 0 0 1 0 0 0 0 0 0
9 8 0 0 0 0 1 0 0 0 0 0
9 0 0 0 0 0 0 1 0 0 0
Storing undirected trees
adjacency matrix
representation
0 1 2 3 4 5 6 7 8 9
0 0 0 1 0 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 0 0 0
1 2 0 0 0 1 0 0 0 0 0 0
3 0 1 1 0 0 0 1 1 0 0
2 3 4 5 4 0 1 0 0 0 1 0 0 1 0
5 0 0 0 0 1 0 0 0 0 0
6 7 8 6 0 0 0 1 0 0 0 0 0 1
7 0 0 0 1 0 0 0 0 0 0
9 8 0 0 0 0 1 0 0 0 0 0
9 0 0 0 0 0 0 1 0 0 0
In practice, avoid storing a tree as an adjacency
matrix! It’s a huge waste of space to use n2 memory
and only use 2(n-1) of the matrix cells.
Rooted Trees!
One of the more interesting types of
trees is a rooted tree which is a tree
with a designated root node.

Rooted tree Rooted tree Rooted tree


Binary Tree (BT)
Related to rooted trees are binary trees
which are trees for which every node has
at most two child nodes.

Not a
Binary tree Binary tree binary tree
Binary Search Trees (BST)
Related to binary trees are binary search trees
which are trees which satisfy the BST invariant
which states that for every node x:
[Link] ≤ [Link] ≤ [Link]
6
6
3
2 7
3 8
2
1 4 9
1 1 7 9

3 5 8
Not a BST
BST BST
Binary Search Trees (BST)
It’s often useful to require uniqueness on the
node values in your tree. Change the invariant
to be strictly < rather than ≤:
[Link] < [Link] < [Link]
6
6
3
2 7
3 8
2
1 4 9
1 1 7 9

3 5 8
Not a BST
BST BST
Storing rooted trees
Rooted trees are most naturally defined
recursively in a top-down manner.
Storing rooted trees
In practice, you always maintain a pointer
reference to the root node so that you can
access the tree and its contents.

root node
Storing rooted trees
Each node also has access to a list
of all its children.

child nodes
Storing rooted trees
Sometimes it’s also useful to maintain a
pointer to a node’s parent node effectively
making edges bidirectional.

parent

current
node
Storing rooted trees
However, this isn’t usually necessary
because you can access a node’s parent on
a recursive function's callback.
Storing rooted trees
If your tree is a binary tree, you can store
it in a flattened array.

This trick also works for any n-ary tree


Storing rooted trees
In this flattened array representation, each
node has an assigned index position based on
where it is in the tree.
9 0

i
8 7 1 2

6 5 1 2 3 4 5 6

2 3 4 2 1 7 8 9 10 11 12 13 14

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
9 8 7 6 5 1 2 ∅ 2 3 4 ∅ ∅ 2 1

This trick also works for any n-ary tree


Storing rooted trees
In this flattened array representation, each
node has an assigned index position based on
where it is in the tree.
9 0
i
8 7 1 2

6 5 1 2 3 4 5 6

2 3 4 2 1 7 8 9 10 11 12 13 14

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
9 8 7 6 5 1 2 ∅ 2 3 4 ∅ ∅ 2 1

This trick also works for any n-ary tree


Storing rooted trees
Even nodes which aren’t currently present have an
index because they can be mapped back to a unique
position in the "index tree" (gray tree).
9 0

8 7 1 2

6 5 1 2 3 4 5 i 6

2 3 4 2 1 7 8 9 10 11 12 13 14
index tree

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
9 8 7 6 5 1 2 ∅ 2 3 4 ∅ ∅ 2 1

This trick also works for any n-ary tree


Storing rooted trees
The root node is always at index 0 and the
children of the current node i are accessed
relative to position i.
9
Let i be the index of the
8 7 current node

left node: 2*i + 1


6 5 1 2
right node: 2*i + 2

Reciprocally, the parent of


2 3 4 2 1
node i is: floor((i-1)/2)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
9 8 7 6 5 1 2 ∅ 2 3 4 ∅ ∅ 2 1

This trick also works for any n-ary tree


Storing rooted trees
The root node is always at index 0 and the
children of the current node i are accessed
relative to position i.
9
Let i be the index of the
8 7 current node

left node: 2*i + 1


6 5 1 2
right node: 2*i + 2

Reciprocally, the parent of


2 3 4 2 1
node i is: floor((i-1)/2)

i
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
9 8 7 6 5 1 2 ∅ 2 3 4 ∅ ∅ 2 1

This trick also works for any n-ary tree


Next Video: beginner tree algorithms
Graph Theory
Video Series
Beginner tree
algorithms
William Fiset
Problem 1: leaf node sum
What is the sum of all the leaf node
values in a tree?
5

4 3

1 -6 0 7 -4

2 9 8
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8 - 4 = 9
5

4 3

1 -6 0 7 -4

2 9 8
5

4 3

1 -6 0 7 -4

2 9 8

When dealing with rooted trees you begin


with having a reference to the root node as
a starting point for most algorithms.
5

4 3

1 -6 0 7 -4

2 9 8
5

4 3

1 -6 0 7 -4

2 9 8
5

4 3

1 -6 0 7 -4

2 9 8
5

4 3

1 -6 0 7 -4

2 9 8

2
5

4 3

1 -6 0 7 -4

2 9 8

2
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8 - 4
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8 - 4
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8 - 4
5

4 3

1 -6 0 7 -4

2 9 8

2 + 9 - 6 + 0 + 8 - 4 = 9
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
# Sums up leaf node values in a tree.
# Call function like: leafSum(root)
function leafSum(node):
# Handle empty tree case
if node == null:
return 0
if isLeaf(node):
return [Link]()
total = 0
for child in [Link]():
total += leafSum(child)
return total

function isLeaf(node):
return [Link]().size() == 0
Problem 2: Tree Height
Find the height of a binary tree. The height
of a tree is the number of edges from the root
to the lowest leaf.

height 0
height 1

height 3
Let h(x) be the height of the subtree
rooted at node x.

b c

e
Let h(x) be the height of the subtree
rooted at node x.

b c

h(a) = 3, h(b) = 2, h(c) = 1, h(d) = 1, h(e) = 0


By themselves, leaf nodes such as node e
don't have children, so they don’t add any
additional height to the tree.

b c

As a base case we can conclude that:


h(leaf node) = 0
Assuming node x is not a leaf node, we’re able
to formulate a recurrence for the height:
h(x) = max(h([Link]), h([Link])) + 1

b c

e
?

? ?

? ? ? ?

? ?
?

? ?

? ? ? ?

? ?
?

? ?

? ? ? ?

? ?
?

? ?

? ? 0 ?

? ?

Leaf node has a height of 0


?

? ?

? ? 0 ?

? ?
?

? ?

? ? 0 0

? ?

Leaf node has a height of 0


?

? 1

? ? 0 0

? ?

height = max(0, 0) + 1 = 1
?

? 1

? ? 0 0

? ?
?

? 1

? ? 0 0

? ?
?

? 1

? 0 0 0

? ?

Leaf node has a height of 0


?

? 1

? 0 0 0

? ?
?

? 1

? 0 0 0

? ?
?

? 1

? 0 0 0

0 ?

Leaf node has a height of 0


?

? 1

? 0 0 0

0 ?
?

? 1

? 0 0 0

0 0

Leaf node has a height of 0


?

? 1

1 0 0 0

0 0

height = max(0, 0) + 1 = 1
?

2 1

1 0 0 0

0 0

height = max(1, 0) + 1 = 2
3

2 1

1 0 0 0

0 0

height = max(2, 1) + 1 = 3
3

2 1

1 0 0 0

0 0
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Handle empty tree case
if node == null:
return -1

# Identify leaf nodes and return zero


if [Link] == null and [Link] == null:
return 0

return max(treeHeight([Link]),
treeHeight([Link])) + 1
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Handle empty tree case
if node == null:
return -1

# Identify leaf nodes and return zero


if [Link] == null and [Link] == null:
return 0

return max(treeHeight([Link]),
treeHeight([Link])) + 1
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Handle empty tree case
if node == null:
return -1

# Identify leaf nodes and return zero


if [Link] == null and [Link] == null:
return 0

return max(treeHeight([Link]),
treeHeight([Link])) + 1
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Handle empty tree case
if node == null:
return -1

# Identify leaf nodes and return zero


if [Link] == null and [Link] == null:
return 0

return max(treeHeight([Link]),
treeHeight([Link])) + 1
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Handle empty tree case
if node == null:
return -1

# Identify leaf nodes and return zero


if [Link] == null and [Link] == null:
return 0

return max(treeHeight([Link]),
treeHeight([Link])) + 1
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Handle empty tree case
if node == null:
return -1

# Identify leaf nodes and return zero


if [Link] == null and [Link] == null:
return 0

return max(treeHeight([Link]),
treeHeight([Link])) + 1
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Return -1 when we hit a null node
# to correct for the right height.
if node == null:
return -1

return max(treeHeight([Link]),
treeHeight([Link])) + 1
Notice that if we visit the null nodes
our tree is one unit taller.
When we go down the tree we need to correct
for the height added by the null nodes.
-1
+1

-1
+1

+1

-1
+1

+1

+1

-1
+1

+1

+1

+1

-1
+1

+1

+1

+1

-1

1 + 1 + 1 + 1 - 1 = 3
# The height of a tree is the number of
# edges from the root to the lowest leaf.
function treeHeight(node):
# Return -1 when we hit a null node
# to correct for the right height.
if node == null:
return -1

return max(treeHeight([Link]),
treeHeight([Link])) + 1
Next Video: rooting a tree
Graph Theory
Video Series
Rooting a
tree
William Fiset
Rooting a tree
Sometimes it’s useful to root an undirected
tree to add structure to the problem you’re
trying to solve.

2 Undirected graph
adjacency list:
3
0 1 0 -> [2, 1, 5]
1 -> [0]
2 -> [3, 0]
4 5 3 -> [2]
4 -> [5]
5 -> [4, 6, 0]
6
6 -> [5]
Rooting a tree
Sometimes it’s useful to root an undirected
tree to add structure to the problem you’re
trying to solve.

3 0
0 1
2 1 5
4 5
3 4 6
6
Rooting a tree
Conceptually this is like "picking up" the
tree by a specific node and having all the
edges point downwards.

3 0
0 1
2 1 5
4 5
3 4 6
6
Rooting a tree

You can root a tree using any of its nodes.

3 5
0 1
0 4 6
4 5
1 2
6
3
In some situations it’s also useful to
keep have a reference to the parent
node in order to walk up the tree.

3 5
0 1
0 4 6
4 5
1 2
6
3
Rooting a tree is easily done depth first.

3
0 1

4 5

6
Rooting a tree is easily done depth first.

3 0
0 1

4 5

6
Rooting a tree is easily done depth first.

3 0
0 1

4 5

6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5

6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5

6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6
6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6
6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6
6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1 2
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1 2
4 5
6 4
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1 2
4 5
6 4 3
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1 2
4 5
6 4 3
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1 2
4 5
6 4 3
6
Rooting a tree is easily done depth first.

3 0
0 1
5 1 2
4 5
6 4 3
6
Rooting tree pseudocode

# TreeNode object structure.


class TreeNode:
# Unique integer id to identify this node.
int id;

# Pointer to parent TreeNode reference. Only the


# root node has a null parent TreeNode reference.
TreeNode parent;

# List of pointers to child TreeNodes.


TreeNode[] children;
Rooting tree pseudocode

# TreeNode object structure.


class TreeNode:
# Unique integer id to identify this node.
int id;

# Pointer to parent TreeNode reference. Only the


# root node has a null parent TreeNode reference.
TreeNode parent;

# List of pointers to child TreeNodes.


TreeNode[] children;
Rooting tree pseudocode

# TreeNode object structure.


class TreeNode:
# Unique integer id to identify this node.
int id;

# Pointer to parent TreeNode reference. Only the


# root node has a null parent TreeNode reference.
TreeNode parent;

# List of pointers to child TreeNodes.


TreeNode[] children;
Rooting tree pseudocode

# TreeNode object structure.


class TreeNode:
# Unique integer id to identify this node.
int id;

# Pointer to parent TreeNode reference. Only the


# root node has a null parent TreeNode reference.
TreeNode parent;

# List of pointers to child TreeNodes.


TreeNode[] children;
Rooting tree pseudocode

# TreeNode object structure.


class TreeNode:
# Unique integer id to identify this node.
int id;

# Pointer to parent TreeNode reference. Only the


# root node has a null parent TreeNode reference.
TreeNode parent;

# List of pointers to child TreeNodes.


TreeNode[] children;
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, []) root node has
return buildTree(g, root, null) no parent!
# Build tree recursively depth first.
function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Rooting tree pseudocode
# g is the graph/tree represented as an adjacency
# list with undirected edges. If there’s an edge between
# (u, v) there’s also an edge between (v, u).
# rootId is the id of the node to root the tree from.
function rootTree(g, rootId = 0):
root = TreeNode(rootId, null, [])
return buildTree(g, root, null)

# Build tree recursively depth first.


function buildTree(g, node, parent):
for childId in g[[Link]]:
# Avoid adding an edge pointing back to the parent.
if parent != null and childId == [Link]:
continue
child = TreeNode(childId, node, [])
[Link](child)
buildTree(g, child, node)
return node
Graph Theory
Video Series
Center(s) of
a tree

William Fiset
Center(s) of undirected tree
An interesting problem when you have an
undirected tree is finding the tree’s center
node(s). This could come in handy if we wanted
to select a good node to root our tree 😉
Center(s) of undirected tree
An interesting problem when you have an
undirected tree is finding the tree’s center
node(s). This could come in handy if we wanted
to select a good node to root our tree 😉

center(s)
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Notice that the center is always the middle
vertex or middle two vertices in every
longest path along the tree.
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Notice that the center is always the middle
vertex or middle two vertices in every
longest path along the tree.
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Notice that the center is always the middle
vertex or middle two vertices in every
longest path along the tree.
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Notice that the center is always the middle
vertex or middle two vertices in every
longest path along the tree.
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Notice that the center is always the middle
vertex or middle two vertices in every
longest path along the tree.
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Notice that the center is always the middle
vertex or middle two vertices in every
longest path along the tree.
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Another approach to find the center is to
iteratively pick off each leaf node layer
like we were peeling an onion.
Center(s) of undirected tree
1
1 0 9 1
4
3
4
2 1 2 3

3 6 5
1

7 8 1
1
The orange circles represent the degree of
each node. Observe that each leaf node will
have a degree of 1.
Center(s) of undirected tree
1
1 0 9 1
4
3
4
2 1 2 3

3 6 5
1

7 8 1
1
Center(s) of undirected tree
0
0 0 9 0
4
1
3
1 1 2 3

1 6 5
0

7 8 0
0

As we prune nodes also reduce the


node degree values.
Center(s) of undirected tree
0
0 0 9 0
4
1
3
1 1 2 3

1 6 5
0

7 8 0
0
Center(s) of undirected tree
0
0 0 9 0
4
0
0
0 1 2 3

0 6 5
0

7 8 0
0
Center(s) of undirected tree

0 9
4

1 2 3

6 5

7 8
Center(s) of undirected tree
0

2 3 4 5

6 7 8

9
Center(s) of undirected tree
0 1
3
1
4 3
1 2 3 4 5 1

6 7 8
2
1 1

9
1
Center(s) of undirected tree
0 1
3
1
4 3
1 2 3 4 5 1

6 7 8
2
1 1

9
1
Center(s) of undirected tree
0 0
2
1
2 1
0 2 3 4 5 0

6 7 8
1
0 0

9
0
Center(s) of undirected tree
0 0
2
1
2 1
0 2 3 4 5 0

6 7 8
1
0 0

9
0
Center(s) of undirected tree
0 0
1
1
1 0
0 2 3 4 5 0

6 7 8
0
0 0

9
0
Center(s) of undirected tree
0

2 3 4 5

6 7 8

9
Some trees have two centers
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
# g = tree represented as an undirected graph
function treeCenters(g):
n = [Link]()
degree = [0, 0, …, 0] # size n
leaves = []
for (i = 0; i < n; i++):
degree[i] = g[i].size()
if degree[i] == 0 or degree[i] == 1:
[Link](i)
degree[i] = 0
count = [Link]()
while count < n:
new_leaves = []
for (node : leaves):
for (neighbor : g[node]):
degree[neighbor] = degree[neighbor] - 1
if degree[neighbor] == 1:
new_leaves.add(neighbor)
degree[node] = 0
count += new_leaves.size()
leaves = new_leaves
return leaves # center(s)
Graph Theory
Video Series
Isomorphisms
in trees
A question of equality

William Fiset
Graph Isomorphism
The question of asking whether two graphs
G1 and G2 are isomorphic is asking whether
they are structurally the same.
0 a

e b
4 1

3 2 d c
G1 G2

Even though G1 and G2 are labelled


differently and may appear different they
are structurally the same graph.
Graph Isomorphism
We can also define the notion of a graph
isomorphism more rigorously:

G1(V1, E1) and G2(V2, E2) are isomorphic if


there exists a bijection φ between the sets
V1 -> V2 such that:

∀ u,v ∈ V1, (u,v) ∈ E1 ⟺ (φ(u),φ(v)) ∈ E2

In simple terms, for an isomorphism to exist


there needs to be a function φ which can map
all the nodes/edges in G1 to G2 and vice-versa.
Graph Isomorphism
Determining if two graphs are isomorphic is
not only not obvious to the human eye, but
also a difficult problem for computers.

0
1 4
1

2 3

0 2 5 7
4 5

6 7
3 6

It is still an open question as to whether the


graph isomorphism problem is NP complete. However,
many polynomial time isomorphism algorithms exist
for graph subclasses such as trees.
Isomorphic Trees
Isomorphic Trees
tree 1 tree 2
0 3

0
1 4

2 5

3 4 5

Q: Are these trees isomorphic?


Isomorphic Trees
tree 1 tree 2
0 3

0
1 4

2 5

3 4 5

A: no, these trees are structurally different.


Isomorphic Trees
tree 3 tree 4
6 0 1 1

2 0 2

3 5 3 4

4 6 5

Q: Are these trees isomorphic?


Isomorphic Trees
tree 3 tree 4
6 0 1 1

2 0 2

3 5 3 4

4 6 5

Yes, one possible label mapping is:


6->0, 1->1, 0->2, 2->3, 5->4, 3->5, 4->6
Identifying Isomorphic Trees

There are several very quick probabilistic


(usually hash or heuristic based) algorithms
for identifying isomorphic trees. These tend
to be fast, but also error prone due to hash
collisions in a limited integer space.

The method we’ll be looking at today involves


serializing a tree into a unique encoding.
This unique encoding is simply a unique
string that represents a tree, if another
tree has the same encoding then they are
isomorphic.
Identifying Isomorphic Trees
We can directly serialize an unrooted tree,
but in practice serializing a rooted tree
is typically easier code wise.
However, one caveat to watch out for if
we’re going to root our two trees T1 and T2
to check if they’re isomorphic is to ensure
that the same root node is selected in both
trees before serializing/encoding the trees.
5
5
0
T1 3
T2
?
1 4 T1 ≅ T2 3 4

2 0 1 2
Identifying Isomorphic Trees
To select a common node between both trees
we can use what we learned from finding the
center(s) of a tree to help ourselves.

<insert video frame>


5
0
T1 3 5
T2

1 4 3 4

2
0 1 2
5
0
T1 3 5
T2

1 4 3 4

2
0 1 2

Find the center(s) of the original tree. We’ll


see how to handle the case where either tree
can have more than 1 center shortly.
5
0
T1 3 5
T2

1 4 3 4

2
0 1 2

4 2

1 3 1 4

0 2 5 0 3 5

Root the tree at the center node.


5
0
T1 3 5
T2

1 4 3 4

2
0 1 2

4 2

1 3 1 4

0 2 5 0 3 5

((()())(())) ((()())(()))

Generate the encoding for each tree and compare


the serialized trees for equality.
5
0
T1 3 5
T2

1 4 3 4

2
0 1 2

4 2

1 3 1 4

0 2 5 0 3 5

000101100111 000101100111
The tree encoding is simply a sequence of left '(' and
right ')' brackets. However, you can also think of them
as 1’s and 0’s (i.e a large number) if you prefer.
5
0
T1 3 5
T2

1 4 3 4

2
0 1 2

4 2

1 3 1 4

0 2 5 0 3 5

((()())(())) ((()())(()))
It should also be possible to reconstruct
the tree solely from the encoding. This is
left as an exercise to the reader… 😛
Generating the tree encoding

The AHU (Aho, Hopcroft, Ullman) algorithm is


a clever serialization technique for
representing a tree as a unique string.

Unlike many tree isomorphism invariants and


heuristics, AHU is able to capture a
complete history of a tree’s degree spectrum
and structure ensuring a deterministic
method of checking for tree isomorphisms.

Let’s have a closer look…


Tree Encoding

2 1 3

6 7 4 5 8

9
Tree Encoding
Start by assigning all leaf nodes
Knuth tuples: '()'
0

2 1 3

6 7 4 5 8
() () () ()

9
()
Tree Encoding
Start by assigning all leaf nodes
Knuth tuples: '()'
0

2 1 3

6 7 4 5 8
() () () ()

9
()
Tree Encoding
Process all nodes with grayed out children and
combine the labels of their child nodes and
wrap them in brackets.
0

(()()) 2 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding
Process all nodes with grayed out children and
combine the labels of their child nodes and
wrap them in brackets.
0

(()()) 2 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding

(()()) 2 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding

(()()) 2 ((())()) 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding
Notice that the labels get sorted when
combined, this is important.
0

(()()) 2 ((())()) 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding
Notice that the labels get sorted when
combined, this is important.
0

(()()) 2 ((())()) 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding

(((())())(()())(()))
0

(()()) 2 ((())()) 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding

(((())())(()())(()))
0

(()()) 2 ((())()) 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding

(((())())(()())(()))
0

(()()) 2 ((())()) 1 (()) 3

6 7 4 (()) 5 8
() () () ()

9
()
Tree Encoding Summary

In summary of what we did for AHU:

• Leaf nodes are assigned Knuth tuples


'()' to begin with.

• Every time you move up a layer the labels


of the previous subtrees get sorted
lexicographically and wrapped in brackets.

• You cannot process a node until you have


processed all its children.
Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Unrooted tree encoding pseudocode
Rooted trees are stored recursively in
TreeNode objects:

# TreeNode object structure.


class TreeNode:
# Unique integer id to identify this node.
int id;

# Pointer to parent TreeNode reference. Only the


# root node has a null parent TreeNode reference.
TreeNode parent;

# List of pointers to child TreeNodes.


TreeNode[] children;
Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Unrooted tree encoding pseudocode
function encode(node):
if node == null:
return ""

labels = []
for child in [Link]():
[Link](encode(child))

# Regular lexicographic sort


sort(labels)

result = ""
for label in labels:
result += label

return "(" + result + ")"


Unrooted tree encoding pseudocode
function encode(node):
if node == null:
return ""

labels = []
for child in [Link]():
[Link](encode(child))

# Regular lexicographic sort


sort(labels)

result = ""
for label in labels:
result += label

return "(" + result + ")"


Unrooted tree encoding pseudocode
function encode(node):
if node == null:
return ""

labels = []
for child in [Link]():
[Link](encode(child))

# Regular lexicographic sort


sort(labels)

result = ""
for label in labels:
result += label

return "(" + result + ")"


Unrooted tree encoding pseudocode
function encode(node):
if node == null:
return ""

labels = []
for child in [Link]():
[Link](encode(child))

# Regular lexicographic sort


sort(labels)

result = ""
for label in labels:
result += label

return "(" + result + ")"


Unrooted tree encoding pseudocode
function encode(node):
if node == null:
return ""

labels = []
for child in [Link]():
[Link](encode(child))

# Regular lexicographic sort


sort(labels)

result = ""
for label in labels:
result += label

return "(" + result + ")"


Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Unrooted tree encoding pseudocode
# Returns whether two trees are isomorphic.
# Parameters tree1 and tree2 are undirected trees
# stored as adjacency lists.
function treesAreIsomorphic(tree1, tree2):
tree1_centers = treeCenters(tree1)
tree2_centers = treeCenters(tree2)

tree1_rooted = rootTree(tree1, tree1_centers[0])


tree1_encoded = encode(tree1_rooted)

for center in tree2_centers:


tree2_rooted = rootTree(tree2, center)
tree2_encoded = encode(tree2_rooted)
# Two trees are isomorphic if their encoded
# canonical forms are equal.
if tree1_encoded == tree2_encoded:
return True
return False
Graph Theory
Video Series
Isomorphisms in
trees source code
A question of equality

William Fiset
Previous video explaining
identifying isomorphic trees:
Source Code Link
Implementation source code can
be found at the following link:
[Link]/williamfiset/algorithms

Link in the description below:


Graph Theory
Video Series
Lowest Common
Ancestor
William Fiset
Definition

What is a LCA?

Where is it used/found?

Give examples, maybe 2 or 3? Family tree,


Understanding LCA

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(13, 14) = 2

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(13, 14) = 2

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(10, 16) = 5

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(10, 16) = 5

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(9, 11) = 0

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(9, 11) = 0

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
You can also find the LCA of more than 2 nodes

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(10, LCA(12, 16)) = 2

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Understanding LCA
LCA(10, LCA(12, 16)) = 2

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
Situation matters
There are lots of considerations to take
into account when solving the LCA problem
which should change how you choose to
tackle the problem.
Situation matters

Question 1: How is the tree stored?

First of all, you're going to need a rooted


tree to be able to find the LCA of two
nodes.

Is the tree a regular rooted tree, or a


binary tree? A binary search tree? Does the
tree have parent pointer references?

The only reason you’d care about whether


your tree is a BST is because it makes it
easier to search.
Situation matters
Question 2:
Do you already have a reference to the nodes
in the tree or do you need to find them?

Often, you can set yourself up in a position


where you would know the reference/id of the
nodes to query, otherwise you need to search
the tree which in the worst of scenarios is
O(n).
Situation matters

Question 3:
Is the tree static or dynamic? I.e, can
nodes be added or removed?

Static trees are typically easier to work


with, but there are algorithms which can
handle dynamic trees quite well.
Situation matters

Question 4:
Do you need an online or offline algorithm?

That is, do you know all the LCA queries in


advance? Or do you need to be able to
dynamically find the LCA?
Various LCA methods

todo(william): investigate Euler tour method


with minimum range query

Tarjan’s offline method with the union


find seems interesting

todo(william): implement light heavy


decomposition and verify that
dynamically adding nodes can be done
in O(1) or even O(logn)
Various LCA methods

Mention this next method (Euler tour + sparse


table LCA method) works best with static trees

Rooted tree, Static tree, have node


references, Online algorithm
LCA on a static tree

1 2

3 4 5 6 7

8 9 10 11 12 13

14 15 16
0
0

1 2 1

3 2 3

tour: [0,1,0,2,3,2,0] tour: [0,1,2,1,3,1,0]

Start the Eulerian tour (Eulerian circuit) at the


root node, visits all edges (assume white edges are
undirected), and finally return to the root node.

An Euler tour on a tree requires visiting 2 nodes per


edge, plus 1 additional visit for the start node:

2*(n-1) + 1 = 2n - 2 + 1 = 2n - 1 nodes
0

1 2

3 4 5

0 1 2 3 4 5 6 7 8 9 10 11 12
depth
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes
0 Depth 0

1 2 Depth 1

3 4 5 Depth 2

6 Depth 3

0 1 2 3 4 5 6 7 8 9 10 11 12
depth
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes
0

1 2

3 4 5

0 1 2 3 4 5 6 7 8 9 10 11 12
depth
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes
0
0

1 2

3 4 5

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0
0
0

1 1 2

3 4 5

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1
0
0

1 1 2

3 4 5
2

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3
0
0

1 1 2
3

3 4 5
2

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1
0
0
4
1 1 2
3

3 4 5
2

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0
0
0
4
1 1 2
3 5

3 4 5
2

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2
0
0
4
1 1 2
3 5

6
3 4 5
2

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4
0
0
4
1 1 2
3 5

6
3 4 5
2

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6
0
0
4
1 1 2
3 5

6
3 4 8 5
2

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4
0
0
4
1 1 2
3 5
9
6
3 4 8 5
2

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4 2
0
0
4
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4 2 5
0
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4 2 5 2
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1 0
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4 2 5 2 0
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1 0
0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4 2 5 2 0
0 12
0 Q: What is LCA(6, 5)?
4 11
1 1 2 1. Find the index position value for the
3 5
nodes `a` and `b` (5 and 6 respectably)
9
6
3 4 8 5
2. Using the depth array, find the
2 10 index of the minimum value in the range
6 of the indices obtained in step 1
7
3. Using the index obtained in step 2,
index into the `nodes` array containing
the tree node data.

0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1 0

0 1 2 3 4 5 6 7 8 9 10 11 12
nodes 0 1 3 1 0 2 4 6 4 2 5 2 0
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
If you recall, step 1 was to find the index position
value for the nodes the two nodes with ids `a` and `b`.

However, an issue we soon run into is that there are


2n - 1 nodes index positions in the Euler tour, and
only n nodes in total, so a perfect 1 to 1 reverse
mapping isn’t possible.
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7

For example, the inverse mapping of node 1 could map


to either index 1 or index 3 in the Euler tour.
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7

Similarly, the inverse mapping for node 2 could map


to either index 5, 9 or 11 in the Euler tour.
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7

Now, suppose we wanted to query the lowest common


ancestor for nodes 1 and 2, which index values
would want to choose for each node?
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7

The answer is that it doesn’t matter, any of the


inverse index values will do. However, in practice I
find that it is easiest to select the last encountered
index while doing the Euler tour.
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
The reason the selection of the inverse index mapping
doesn’t matter is that it will not affect the value
obtained from the Range Minimum Query (RMQ) in step 2
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1 0
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7
Suppose that for the LCA(1, 2) we had selected index
1 for node 1 and index 9 for node 2, meaning the
range [1, 9] in the depth array for the RMQ.
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1 0
0 12
0
4 11
1 1 2
3 5
9
6
3 4 8 5
2 10

6
7

You may think the range [3, 5] would be better since


the interval is smaller. However, this doesn’t
matter since RMQ take O(1) with a sparse table.
0 1 2 3 4 5 6 7 8 9 10 11 12
depth 0 1 2 1 0 1 2 3 2 1 2 1 0
Graph Theory
Video Series
Heavy-Light
Decomposition
(Heavy path decomposition)

Micah Stairs | William Fiset


Graph Theory
Video Series
Tree Centroid
Decomposition
TODO: maybe add some nifty divide
and conquer quote

William Fiset

You might also like