4.3 - Fundamentals of algorithms

Question 1

What is in-order traversal and what is it used for?

Answer 1

Each node is visitedbetween each of its subtrees (flag under nodes)

Returns the values of a binary search tree in ascending order

Question 2

What is pre-order traversal and what is it used for?

Answer 2

Each node is visitedbefore the algorithm traverses either of the node’s subtrees (flag left of nodes)

Creates a copy of the tree

Question 3

What is post-order traversal and what are its 2 uses?

Answer 3

Each node is visitedafter both of its subtrees (flag right of nodes)

• Can be used to delete a tree’s contents
• Obtains the post-fix expression of an expression tree

Question 4

How do you use a stack to convert a post-fix expression into an in-fix expression (or evaluate a post-fix expression)? (5 points)

Answer 4

1. Traverse the expression from left to right
2. Push every operand into the stack until you reach an operator.
3. Pop the last 2 operands pushed into the stack and apply the operator to the 2 operands (operand 2, operator, operand 1).
4. Put brackets around the expression created/evaluate it and push it into the stack.
5. Continue steps 2-4 until you reach the end and pop the result.

Question 5

What are the 3 advantages of Reverse Polish Notation?

Answer 5

Doesn’t need brackets - no need for BODMAS

Simpler for a machine to evaluate

No need for backtracking in evaluation - operators appear in the order required for computation and can be evaluated from left to right