Topics to discuss

• Breadth-first search algorithm and what it would look like.
• How do you generalize breadth-first (preorder/postorder, left/right)?
• How do you generalize depth-first (preorder/postorder/inorder, left/right)?

Tree

                   moosey
                  /      \ 
               emu       salamander
              /   \          /    \
             ant  gibbon  puma    zebra
                                  /
                                yak

Depth-first, left-to-right, preorder

Output: monkey, emu, ant, gibbon, salmander, ...

Stack s; s.push(root);

while (!s.empty() val = s.pop() if val is a string print it otherwise push right subtree push left subtree push value

How do we make this postorder?

    push value
    push right subtree
    push left subtree

How do we make this inorder?

    push right subtree
    push value
    push left subtree

How do we make this right-to-left, preorder?

    push left subtree
    push right subtree
    push value

Let's try it

    Stack: Node:moose TOP
    Stack: Node:emu Node:salamander String:moose TOP
    Stack: Node:emu Node:salamander TOP
    Stack: Node:emu Node:puma Node:zebra String:salamander TOP
    Stack: Node:emu Node:puma Node:zebra TOP
    Stack: Node:emu Node:puma Node:yak String:zebra TOP
    Stack: Node:emu Node:puma Node:yak TOP
    Stack: Node:emu Node:puma String:yak TOP
    Stack: Node:emu Node:puma TOP

    Output: moose, salamander, zebra, yak

Generalized .. because stacks are backwards

• For preorder (print/process node before children), we push the value last.
• For postorder (print/process node after children), we push the value first.
• For inorder (print/process node between children), we push the value between the children.
• For left-to-right, push the right before the left.
• For right-to-left, push the left before the right.

Breadth-First

Goal top down: monkey, emu, salamander, ant, gibbon, puma, zebra, yak

Big idea from the depth first: Shove values in a linear structure.

So, let's try a queue.

Queue q; q.enqueue(root);

while (!q.empty() val = q.dequeue() if val is a string print it otherwise enqueue value enqueue left subtree enqueue right subtree

Let's try it

    Queue: FRONT Node:moose
    Queue: FRONT String:moose Node:emu Node:salamander
    Queue: FRONT Node:emu Node:salamander
    Queue: FRONT Node:salamander String:emu Node:ant Node:gibbon
    Queue: FRONT String:emu Node:ant Node:gibbon String:salamander Node:puma Node:zebra
    Queue: FRONT Node:ant Node:gibbon String:salamander Node:puma Node:zebra
    Queue: FRONT Node:gibbon String:salamander Node:puma Node:zebra String:ant
    Queue: FRONT String:salamander Node:puma Node:zebra String:ant String:gibbon
    Queue: FRONT Node:puma Node:zebra String:ant String:gibbon
    Queue: FRONT Node:zebra String:ant String:gibbon String:puma
    Queue: FRONT String:ant String:gibbon String:puma String:zebra Node:yak

    Output: moose emu salamander

Can we do postorder this way? Not that Sam can figure.

while (!q.empty() val = q.dequeue() if val is a string print it otherwise enqueue left subtree enqueue right subtree enqueue value

    Queue: FRONT Node:moose
    Queue: FRONT Node:emu Node:salamander String:moose
    Queue: FRONT Node:salamander String:moose Node:ant Node:gibbon String:emu
    Queue: FRONT String:moose Node:ant Node:gibbon String:emu Node:puma Node:zebra String:salamander

Solution? Put the strings in a stack? And reverse the order we enqueue?