Tree Traversals

Question 1

What is the definition of a tree traversal?

Answer 1

An organized walk that visits every node once (typically, to perform an operation at each node)

This works for any tree, it does not have to be binary

Question 2

What are the 3 standard ways to traverse a tree?

Draw a visual representation of information we can access in a tree node

Answer 2

1. preorder
2. postorder
3. inorder

Question 3

Define a preorder traversal?

What is another name?

When would you use one?

Answer 3

Use a pre-order traversal when the tasks performed at the children of a node depend on the results of the task performed at the node itself(their parent)

Question 4

What would be the print out for this data in a preorder traversal?

Answer 4

20, 4, 7, 19, 47, 44, 21, 73

Question 5

Define depth of a node

In general, how would you compute a node’s depth with a pre-order traversal?

1. What is the depth of the root?
2. What is the depth of the child of the root?
3. What is the depth of the grandchild of the root?

Answer 5

Deph of a node n is the length of the path from the root of the tree to n

• Since a node’s depth is one greater than it’s parent’s depth,
• Computing the depth of a child depends on the result of computing the depth of its parent

1. 1
2. 2
3. 3

Question 6

What would the class Node be if each Node contains a depth instance member?

Answer 6

Question 7

Pre-Order Traversal: Computing Node Depths

What is the code for the public driver and private helper method in the BST class?

Answer 7

Question 8

Pre-Order Traversal: Computing Node Depths

Draw the recursive call map for the following tree

Answer 8

Question 9

Define an inorder traversal

Answer 9

Question 10

What would be the print out for this data in a inorder traversal?

Answer 10

The output of an inorder traveral of a binary search tre is the values of the tree in sorted order:

4, 7, 19, 20, 21, 44, 47, 73

Question 11

Define an Expression Tree and describe how it works:

Answer 11

How it works:

• Constant operands are stored in the leaves
• Operators are stored in the interior node (non-leaf node = interior node)

Question 12

Draw the expression tree for the following:

((4 X 3) - 9 ) + (3 X (1 + 6))

Explain why the parentheses and operation priorities are not needed

Answer 12

The tree itself sets/is the operation priorities, for any arithmetic expression, there is only one corresponding expression tree.

Question 13

What is the corresponding expression trees to the following equations:

1. 2 X 3 + 4
2. 2 X (3 + 4)

Answer 13

Question 14

How can you perform an inorder traversal of an expression tree and ensure you print the correct parentheses?

Answer 14

Question 15

Inorder traversal of an expression tree:

Print the correct parentheses for the following expression tree

Answer 15

(((4 x 3) - 9) + (3 x ( 1 + 6)))

Question 16

Define Postorder Traversal.

What would be it’s application?

Answer 16

Use a post-order traversal when the task you are performing at a node depends on the results of the task performed at its children

Question 17

Postorder Taversal of BST:

Print out each node of the following tree

Answer 17

19, 7, 4, 21, 44, 73, 47, 20

Question 18

In general what is the obvious recursive algorithm to evaluate an expression tree, beginning at the root?

What algorithm is it?

Answer 18

Post-order traversal

Question 19

Evaluating an expression tree with a traversal:

What is the postfix expression of the follow and draw the table of calls

Answer 19

Question 20

How do you implement the code for a traversal?

How do you modify the code to work for pre-order and post-order traversals?

Answer 20