(e) Algorithms for the main data structures

Stack Push Operation

Stack Pop Operation

Queue Enque Operation

Queue Dequeue Operation

How do you perform a depth first (post order) traversal?

1. visit all nodes from left of root node

2. visit all nodes from right of root node

3. visit root node

4. repeat three points for each node visited

How do you perform a depth first (post order) traversal using a bubble around a tree?

• draw bubble around tree

• start from root node

• mark the right side of each node in order

How do you perform a breadth first (pre order) traversal?

• draw bubble around tree

• start from root node

• mark the left side of each node in order

What is an advantage of depth first (post-order) traversal?

• requires less memory than breadth first

• quicker when looking for deep parts of the tree

What is an disadvantage of depth first (post-order) traversal?

• isn’t guaranteed to find the quickest solution + may never find solution

  • have to take precautionsnot to revisit previously visited nodes

How is backtracking used in depth first?

• starts at root node

• goes all the way down one branch to the bottom

• stores which node been visitied/pushes nodes visited onto stack

• when can’t go further

• back tracks to previous nide

• continues to backtrack until node reached w/ unvisitied child nodes

• checks down that branch

Pseudocode for depth first (post-order) traversal on trees

Pseudocode for breadth first (pre-order) traversal on trees