4.3 Fundamentals of algorithms

Not all -> just some

What are the 3 ways of traversing a binary tree?

In-order

Pre-order

Post-order

What are the acronyms for each of the tree traversals?

In-order : LNR

Pre-order : NLR

Post-order : LRN

True or False: You restart the LNR/NLR/LRN at each node ?

True!

What are the uses of In-order traversal?

Outputting an ordered list of contents from a binary tree,

Searching in a Binary Search Tree

What are the uses of Pre-order traversal?

Copying a Tree

What are the uses of Post-order traversal?

Emptying / Deleting a Tree

What are the steps for evaluating RPN ?

1) Start on the LHS of the expression

2) Push numbers onto a stack

3) If operator, pop previous two numbers, evaluate first num added to stack (operator) second num added to stack

4) Push result back onto stack

5) Repeat until a single number (the result) remains on the stack

Give the steps to convert Infix to RPN

1) Push open bracket onto stack

2) Numbers go to output list immediately

3) If operator -with higher precedence than operator on stack already- push onto stack

4) If operator has lower or equal precedence to operator on stack already, pop operator from stack then push new operator

5) Closing bracket pops all operators from stack until open bracket found

6) Expression is converted once stack is empty (so make sure to pop all operators at the end)

Which has higher precedence * or +

*

What is actually meant by an operator having “higher precedence” ?

An operator with higher precedence must be evaluated, regardless of where it is, before one of a lower precedence

When converting infix to RPN, if the stack currently contains a +, what happens when we try to push another + onto the stack?

The first + (of equal precedence) is popped, then the new + is pushed onto the stack

Give the steps for converting RPN to infix

1) Push numbers onto stack

2) If operator, pop previous two numbers, and create a string with brackets : (first number onto stack operator second number onto stack)

3) Push result onto stack

4) Repeat until one item remains on the stack