Chapter 10
Trees

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter10/extra_examples.html - Extra examples with solutions.

10.1 Introduction to Trees

Circuit if begins and ends at same vertex. Simple path/circuit if does not include edge more than once.

Definition 1

Tree is a connected graph with no simple circuits.

Example

G₁, G₂ are trees

G₃ has circuit d, a, b, c, d

G₄ is not connected

Definition

Forest is unconnected trees.

Theorem 1

Tree as undirected graph iff simple path between any two vertices.

Definition 2

Rooted tree has one vertex designated as root and every edge is directed away from the root.

T is undirected graph as a tree, any vertex could be root.

Question 10.1.1

Draw tree T with root b.

 

Definitions by Example

Parent a of g, f, b.	Child g, f, b of a.	Leaf if no children d, e, f, i, k, l, m
Ancestors a, b, c of d.	Siblings g, f, b. h, i, j.	Descendants c, d, e of b. d, e of c.
Internal vertices have children. a, b, c, g, h, j	Subtrees rooted at g, b, c, h, j.

Question 10.1.2

1. b internal?
2. k internal?
3. g subtree root?
4. k descendant of g?
5. d sibling of e?

Definition 3

m-ary tree if every internal vertex has no more than m children. Full m-ary tree if every internal vertex has exactly m children. Binary tree is m-ary tree with m=2.

T₁ full binary           T₂ full 3-ary                        T₃ full 5-ary                        T₄ 3-ary

 

Definition

Left child in (a) of parent a is b in (c) of parent i is k.

Question 10.2.1 - For (a) give:

1. Children of i.
    
2. Ancestors of d.
    
3. Internal vertices (have children).
    
4. Leaf (if no children).
    
5. Siblings of k.

 

Trees as Models

Family tree

Question 10.2.2 - ary of above tree?

 

 

Seven connected processors

Recurrence relations

Edges are labeled with the values of each recurrence term.

a0 = 3 a1 = 4 an = an-1 + an-2

Tree for a4 = a3 + a2

Question 10.3

Determine a₂, a₃, a₄ then draw tree for recurrence relation values, a₀ though a₄:

a₀ = 1

a₁ = 2

a_n = a_n-1 + 2a_n-2

 

Properties of Trees

Theorem 2

n vertices tree has n-1 edges.

Example

Below tree has 7 vertices and 6 edges.

Theorem 3

Full m-ary tree with i internal vertices contains n = mi + 1 vertices.

Example

Above 2-ary tree

3 internal vertices

n = 2 * 3 + 1 = 7 total vertices.

Theorem 4

Full m-ary tree with: (i) n vertices has i = (n-1)/m internal vertices l = [(m-1)n+1]/m leafs. (ii) i internal vertices has n = mi+1 vertices l = (m-1)i+1 leafs. (iii) l leafs has n = (ml-1)/(m-1) vertices i = (l-1)/(m-1) internal vertices.

Example

Full 3-ary tree:

l = 9 leafs

n = (3*9-1)/(3-1) = 13 total vertices        (iii) l leafs has n=(ml-1)/(m-1) vertices

i = (9-1)/(3-1) = 4 internal vertices         (iii) i=(l-1)/(m-1) internal vertices

l = (3-1)*4 + 1 = 9 leafs                         (ii) l=(m-1)i+1 leafs.

Example 9

Chain letter sent to 3 others represented by 3-ary tree, leaf vertices are those not sending letter.

1. How many people have seen letter, including first person, if no duplicates and letter ends after 100 people received but did not send? Total vertices are those who have seen letter.
    
2. How many people sent the letter? Internal vertices are those who sent letter.

 

l=100    Leaf vertices, people receiving but not sending the letter.

(iii) l leafs = 100       m-ary = 3

n = (ml-1)/(m-1) vertices

i = (l-1)/(m-1) internal vertices.

By (iii) n = (3*100-1)/(3-1) = 299/2 = 149 vertices, the number who have seen the letter.

By (iii) i = (100-1)/(3-1) = 99/2 = 49 internal vertices, the number who sent the letter.

 

Definition

Balanced m-ary tree if all leaf vertices are at levels h or h-1.

Example

T₁ is balanced, leafs at level 3 and 4.

T₂ is not balanced, leafs at levels 2, 3, 4.

T₃ is balanced, all leafs at level 3.

 

 

Definition

Height is maximum number of edges from tree root to lowest leaf.

Depth is number of edges a vertex is from the tree root.

Question 10.4.1 - What is the height of:

1. T₁
    
2. T₂
    
3. T₃

 

Theorem 5

mh maximum number of leafs in m-ary tree of height h.

Example

Following 2-ary tree of height 2 has 4 leafs.

m^h = 2² = 4

Example

Full 4-ary tree of height 5 has 1024 leafs.

m^h = 4⁵ = 1024

 

Example

3-ary Height	Maximum leafs mh
0	30 = 1
1	31 = 3
2	32 = 9
3	33 = 27

Question 10.4.2 - By Theorem 5, what is the maximum number of leafs for:

1. T₁
    
2. T₂
    
3. T₃

Theorem 5

mh maximum number of leafs in m-ary tree of height h.

 

 

Corollary 1

h ≥ ⌈logm l⌉for m-ary tree of height h and l leafs. h = ⌈logm l⌉for full and balanced m-ary tree of height h and l leafs.

Example

Below full, balanced 2-ary tree of height 2 has 4 leafs.

h =⌈log₂ 4⌉ = ⌈log₂ 2²⌉ = ⌈2⌉= 2

Example

4-ary tree of height 5 has 1024 leafs maximum.

h ≥ ⌈log₄ 1024⌉ = ⌈log₄ 4⁵⌉ = ⌈5⌉= 5

Question 10.4.3 - By Corollary 1, what is the height of a 2-ary tree with 16 leafs.

Corollary 1

h ≥ ⌈logm l⌉for m-ary tree of height h and l leafs. h = ⌈logm l⌉for full and balanced m-ary tree of height h and l leafs.

 

 

10.2 Applications of Trees

Binary Search Trees

Definition

Binary search tree totally orders vertices.

Example

The following binary tree is totally ordered where all:

1. left children are alphabetically less than the parent,
    
2. right children are alphabetically greater than the parent.

 

Question 10.5 - Is the following a binary search tree?

 

Definition

Binary search tree constructed by adding vertices to maintain a total ordering.

Example

Child vertices:

1. > parent, add to right
    
2. < parent, add to left
    
3. = parent, don't add

Example

Add computer science to the right-bottom figure.

Example

Add item 18 to the figure using Algorithm 1.

Question 10.6 - Use above algorithm to insert: 6   32

 

Decision Trees

Example

8 coins, 1 is counterfeit of lighter weight than other 7 coins.

Same number of coins on balance scale weight either:

left < right           left = right             left > right

3-ary decision.

Fewest possible is 2 weightings as illustrated below:

Weight 1, 2, 3 (left) and 4, 5, 6 (right):

left < right

Weight 1 and 2: either left < right, left = right, or left > right

left = right

Weight 7 and 8: either left < right or left > right

left > right

Weight 4 and 5: either left < right, left = right, or left > right

8 possible outcomes, 8 leafs

coin in leaf is counterfeit, e.g. 3 is counterfeit when 1 and 2 balance.

By Corollary 1:

 h ≥ ⌈log₃ 8⌉ ≈ ⌈1.89⌉= 2

so the decision tree height is at least 2, agreeing with the above figure.

 

Corollary 1

h ≥ ⌉logm l⌉for m-ary tree of height h and l leafs. h =⌈logm l⌉for full and balanced m-ary tree of height h and l leafs.

 

Example

Sorting a, b, c.

P(3,3) = 3! = 6 ways to arrange 3 values

a<b<c

a<c<b

b<a<c

b<c<a

c<a<b

c<b<a

1<2<3

1<3<2

2<1<3

2<3<1

3<1<2

3<2<1

6 leaf vertices in a sort, only one is correctly sorted.

Decision tree for sorting compares 2 values at a time (binary-comparison sort).

2-ary tree.

left > right

left < right

Sorting n has P(n, n) = n! outcomes (leafs).

Number of comparisons (tree height), by Corollary 1: h ≥ ⌉log2 n!⌉ ⌈log2 3!⌉ = ⌈log2 6⌉ ≈ ⌉2.33⌉ = 3 so the height is at least 3, agreeing with the below figure. ⌈log2 n!⌉ is Θ(n log2 n) Graph illustrates that log n! is O(n log n) Means that a binary-comparison sort is Θ(n log2 n). Can do no better.

Example - Sorting numbers 1, 2, 3

 

10.3 Tree Traversal

Universal Address Systems

Traverse tree in lexicographic (dictionary or alphabetical) order:

0<1<1.1<1.2<1.3<2<3<3.1<3.1.1<3.1.2.1<3.1.2.2<3.1.1.3<3.1.2.4<3.1.2<3.1.3<3.2<4<4.1<5<5.1<5.1.1<5.2<5.3

 

Traversal Algorithms

Trees are naturally recursive, each subtree is a tree.

Tree algorithms are recursive, when visiting subtrees.

Example

visitL( T )   if T = null return   list T   visitL ( left T ) Order listed: a, b, e, j   visitR( T )   if T = null return   list T   visitR ( right T )

Question 10.7.1 Execute visitR( T ) on tree above.

 

The following is more in the author's style:

list vertex,

then visit the left subtree.

Algorithm 0.1 Preorder Left Subtree Traversal procedure preLeft( T: ordered rooted tree ) if T = null then return r := root of T list r T := left subtree preLeft( T ) Order listed is: a, b, e, j Question 10.7.2 - Execute preRight( T ): Algorithm 0.3 Preorder Right Subtree Traversal procedure preRight( T: ordered rooted tree ) if T = null then return r := root of T list r T := right subtree preRight( T ) The following: visit left subtrees then list. Algorithm 0.2 Postorder Left Subtree Traversal procedure postLeft( T: ordered rooted tree ) if T = null then return r := root of T T := left subtree postLeft( T ) list r Order listed is: j,e,b,a

Question 10.7.3 - Execute postRight( T ):

Algorithm 0.3 Postorder Right Subtree Traversal procedure postRight( T: ordered rooted tree ) if T = null then return r := root of T T := right subtree postRight( T ) list r

 

Definition 1

Preorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn. Visit r. Visit T1 in preorder. Visit T2 in preorder.   n.  Visit Tn in preorder.

 

Example

Preorder traversal of T visits vertices in the order of:

a, b, e, j, k, n, o, p, f, c, d, g, l, m, h, i

Algorithm 1 Preorder Traversal procedure preorder( T: ordered rooted tree ) r := root of T list r for each child c of r from left to right T( c ) := subtree with c as root preorder( T( c ) )

 

Question 10.7.4 - Give the preorder traversal of:

Definition 1

Preorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.     Visit r.     Visit T1 in preorder.     Visit T2 in preorder.   n+1.  Visit Tn in preorder.

Definition 2

Inorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.     Visit T1 inorder.     Visit r.     Visit T2 inorder.   n+1. Visit Tn inorder.

Inorder traversal of T visits vertices in the order of:

j, e, n, k, o, p, b, f, a, c, l, g, m, h, d, h, i

Algorithm 2 Inorder Traversal procedure inorder( T: ordered rooted tree ) r := root of T if r is leaf then list r else l := first child of r from left to right T( l ) := subtree with l as its root inorder( T( l ) ) list r for each child c of r except for l from left to right T( c ) := subtree with c as root inorder( T( c ) )

 

Question 10.8 - Give the inorder traversal of:

Definition 3

Postorder traversal of tree T rooted at r with left-to-right subtrees T1, T1,..., Tn.     Visit T1 postorder.     Visit T2 postorder.   n.      Visit Tn postorder.   n+1. Visit r.

Postorder traversal of T visits vertices in the order of: j, n, o, p, k, e, f, b, c, l, m, g, h, i, d, a Algorithm 3 Postorder Traversal procedure postorder( T: ordered rooted tree ) r := root of T for each child c of r from left to right T( c ) := subtree with c as root postorder( T( c ) ) list r

Question 10.9 - Give the postorder traversal of:

 

Example

Lexiographic ordering of "newyork" in a binary-search tree.

               n
            /     \
          e        w
           \       /  \
            k    o     y
                   \     
                    r    

void Preorder() {                         System.out.print( key );                      // nekwory           if( left != null) left.Preorder( );           if( right != null) right.Preorder( );      }

void Inorder() {                         if( left != null) left.Inorder( );           System.out.print( key );                      // eknorwy           if( right != null) right.Inorder( );      }

void Postorder() {                        if( left != null) left.Postorder( );           if( right != null) right.Postorder( );           System.out.print( key );                      // keroywn      }

Java Preorder/Inorder/Postorder construction and traversal of binary search tree

class Vertex {      Vertex p, left, right;      char key;        Vertex (char key, Vertex p, Vertex left, Vertex right) {                   this.key=key;    this.p = p;                   this.left = left;   this.right = right;      }                  void Preorder() {               // Traverse preorder           System.out.println( key );           if( left != null) left.Preorder( );           if( right != null) right.Preorder( );      }        void Inorder() {               // Traverse inorder           if( left != null) left.Inorder( );           System.out.println( key );           if( right != null) right.Inorder( );      }      void Postorder() {               // Traverse postorder           if( left != null) left.Postorder( );           if( right != null) right.Postorder( );           System.out.println( key );      }      void Insert(char key) {    // Insert new Vertex            if( key <= this.key)                   if( left != null ) left.Insert( key );                   else left = new Vertex(key, this, null, null);            else                   if( right != null ) right.Insert( key );                   else right = new Vertex(key, this, null, null);       } }   public class VertexFun {      public static void main(String a[]) {            Vertex root = new Vertex( 'n', null, null, null);            root.Insert( 'e' );            root.Insert( 'w' );            root.Insert( 'y' );            root.Insert( 'o' );            root.Insert( 'r' );            root.Insert( 'k' );              root.Inorder();      } }

 

Infix, Prefix, Postfix Notation

Binary tree representing ((x + y) ^ 2) + ((x - 4) / 3)
                                          

Preorder:     + ^ + x y 2 / - x 4 3

Inorder:       x + y ^ 2 + x - 4 / 3

Postorder:    x y + 2 ^ x 4 - 3 / +

 

RPN - Reverse Polish Notation (every operator follows its operands)

Can represent algebraic expressions without parenthesis or precedence.

Example

5 + 2 * 3

in RPN: 5 2 3 * +

Example

(5 + 2) * 3

in RPN: 5 2 + 3 *

Example

1 - 2 * 3 + 4

in RPN:     1 2 3 * - 4 +

Example

5 / ((2 + 3) * 4) − 1

in RPN:    5 2 3 + 4 * / 1 -

Example

5 / 2 + 3 * 4 − 1

in RPN:    5 2 / 3 4 * + 1 -

Converting infix containing +, -, *, and () to RPN requires:

1. writing numbers when encountered,
2. higher precedence operations first,
3. then equal precedence left-to-right.

For a formal algorithm see: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Question 10.10.1

a.    RPN of: 5 + ((1 - 2) * 4) / 3
 

b.    Give the postorder traversal of binary tree representing: 3 * 5 + 8 % 2 

              +

            /    \
  *      %
/   \    /  \

        3     5 8    2

 

Evaluation of RPN

RPN can be evaluated by a simple stack machine.

The following stack algorithm evaluates an expression in RPN.

Evaluate the RPN: 1 2 3 * - 4 +

Try the Java applet to enter expressions in the form specified in the expression grammar, parse, generate RPN, then evaluate the RPN. Source code for the applet is available.

Question 10.10.2

    Evaluate the RPN:     5 4 * 9 3 + - 2 +

 

10.4 Spanning Trees

Definition

Simple graph when each edge connects two different vertices and no two edges connect the same pair of vertices.

Example

Not simple

Simple

Definition 1

Spanning tree of simple graph G is subgraph of G containing every vertex of G.

Example 1

Simple graph not necessarily a tree, below has circuits.

Spanning tree construction from the simple graph

 

Theorem 1

Connected simple graph iff it has a spanning tree.

Proof

Show G connected

1. Assume simple graph G has spanning tree T.
2. T contains every vertex of G.
3. T is a subgraph of G, therefore is a path between every two vertices of T.
4. Since T is a spanning tree of G and a subgraph of G, G is connected.

Show spanning tree

1. Assume G is connected.
2. If G is not a tree, contains simple circuit.
   1. Remove an edge from circuit.
      • Result still contains all vertices of G.
      • Still connected.
   2. Go to 2.
3. G is a connected tree, no simple circuits remain.

Example

Several spanning trees

Example 2

IP Multicasting

 

Depth-First Search

Depth-first search explores to leaf nodes first. Can be used to construct spanning tree.

Example

Starting at e, apply depth-first search.

1. Add e to tree T.

T

2. Visit new vertex adjacent to e alphabetically, add c to T.

T

3. Visit new vertex adjacent to c alphabetically, add a to T.

4. Visit new vertex adjacent to a alphabetically. No new, backup to c.

5. Visit new vertex adjacent to c alphabetically, add b to T.

6. Visit new vertex adjacent to b alphabetically. No new, backup to c.

7. Visit new vertex adjacent to c alphabetically. No new, backup to e.

8. Visit new vertex adjacent to e alphabetically, add d to T.

9. Visit new vertex adjacent to d alphabetically, add f to T.

10. Visit new vertex adjacent to f alphabetically, add g to T.

11. Visit new vertex adjacent to g alphabetically, add h to T.

12. Visit new vertex adjacent to h alphabetically. No new, backup to g.

13-16. Backup to f, d, e and no new vertices, finished.

Example

Start at f and visit adjacent vertices in alphabetical order, perform depth-first search.

visit( f )

procedure visit( v : vertex of G)           -- visit alphabetically     for each vertex w adjacent to v and not yet in T  add vertex w and edge (v, w) to T visit( w )

Connected graph G

Depth-first search tree T with order visited. Vertices added left-to-right.

Question 10.11.1

In below graph, start at c and visit adjacent vertices in alphabetical order, perform depth-first search.

visit( c )

procedure visit( v : vertex of G)           -- visit alphabetically     for each vertex w adjacent to v and not yet in T  add vertex w and edge (v, w) to T visit( w )

Algorithm 1 Depth-First Search procedure DFS( G : connected graph, vertices: v1, v2,...vn)    T := tree consisting of v1    visit( v1 ) procedure visit( v : vertex of G)           -- visit alphabetically     for each vertex w adjacent to v and not yet in T  add vertex w and edge (v, w) to T visit( w )

Example Add v1 = f arbitrarily as root of T. {d,e,g,h} adjacent to f, pick d (alphabetically). T=(V,E) V={f,d} E={(f,d)} {f,e} adjacent to d, f already in T, pick e. T=(V,E) V={f,d,e} E={(f,d), (d,e)} Continue adding {c,a,b} No vertex adjacent to c, not yet in T Backtrack to e No vertex adjacent to e, not yet in T Backtrack to d No vertex adjacent to d, not yet in T Backtrack to f Vertex g and h adjacent to f, not yet in T, pick g. T=(V,E) V={f,d,e,c,a,b,g} E={(f,d),(d,e),(e,c),(c,a),(c,b),(f,g)} :

Question 10.11.2 - Depth-first search to find spanning tree.

Start at c, use alphabetically smaller new letter first.

 

Breadth-First Search

Breadth-first search explores all child nodes first, before exploring deeper.

Example - Starting at e, apply breadth-first search.

0.    Append e to list L.

    L = e

1. Remove first vertex from L, e, and add to tree T.

Append new vertices adjacent to e alphabetically to list L, add to T.

    L = c d f

2. Remove first vertex from L, c.

    Append new vertices adjacent to c alphabetically to list L, add to T.

    L = d f a b

3. Remove first vertex from L, d.

    Append new vertices adjacent to d alphabetically to list L.

    L = f a b

    No change

4. Remove first vertex from L, f.

    Append new vertices adjacent to f alphabetically to list L, add to T.

    L = a b g h

5. Remove first vertex from L, a.

    Append new vertices adjacent to a alphabetically to list L.

    L = b g h

6. Remove first vertex from L, b.

    Append new vertices adjacent to b alphabetically to list L.

    L = g h

7. Remove first vertex from L, g.

    Append new vertices adjacent to g alphabetically to list L.

    L = h

8. Remove first vertex from L, h.

    Append new vertices adjacent to h alphabetically to list L, add to T.

    L = i

9. Remove first vertex from L, i.

    Append new vertices adjacent to i alphabetically to list L

L =

10. L is empty, stop.

    Spanning tree is rooted at starting vertex e.

 

Question 10.12.1 - Breadth-first search to find spanning tree.

Start at f, append alphabetically.

 

Algorithm 2 Breadth-First Search procedure BFS( G : graph, vertices: v1,v2,...vn)   T := tree consisting of v1   L := empty list   put v1 in the list L of unprocessed vertices   while L is not empty remove the first vertex, v, from L for each neighbor w of v (alphabetically) if w not in L and not in T then add w to the end of list L add w and edge (v, w) to T

Example Add v1 = e arbitrarily as root of T. T=(V,E) V={e} E={} L = { } L = { e } v = e {b,d,f,i} neighbors of e L = { b } T=(V,E) V={e,b} E={(e,b)} L = {b, d} T=(V,E) V={e,b,d} E={(e,b), (b,d)} L = {b, d, f} T=(V,E) V={e,b,d,f} E={(e,b), (e,d), (e,f)} L = {b, d, f, i} T=(V,E) V={e,b,d,f,i} E={(e,b), (e,d), (e,f), (e,i)} v = b first of L = {b,d,f,i} {a,c,e} neighbors of b L = {d,f,i,a} T=(V,E) V={e,b,d,f,i,a} E={(e,b),(e,d),(e,f),(e,i),(b,a)} L = {d,f,i,a,c} T=(V,E) V={e,b,d,f,i,a,c} E={(e,b),(e,d),(e,f),(e,i),(b,a),(b,c)}

Question 10.12.2 - Breadth-first search for spanning tree.

Start at c, use alphabetically smaller letter first.

 

Note that in "for each neighbor w of v (alphabetically)", the alphabetically ensures that only one spanning tree will generated but is not necessary to produce a different, valid spanning tree.

Breadth-first search generally produces a spanning tree of lower height than depth-first search.

 

Question 10.13 - Starting at f, apply breadth-first search to:

Question 10.14 - Starting at e, apply depth-first search to: