# Tree Traversals Flashcards

1
Q

What is the definition of a tree traversal?

A

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

2
Q

What are the 3 standard ways to traverse a tree?

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

A
1. preorder
2. postorder
3. inorder
3
Q

Define a preorder traversal?

What is another name?

When would you use one?

A

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)

4
Q

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

A

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

5
Q

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?
A

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
6
Q

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

A
7
Q

Pre-Order Traversal: Computing Node Depths

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

A
8
Q

Pre-Order Traversal: Computing Node Depths

Draw the recursive call map for the following tree

A
9
Q

Define an inorder traversal

A
10
Q

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

A

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

11
Q

Define an Expression Tree and describe how it works:

A

How it works:

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

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

A

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

13
Q

What is the corresponding expression trees to the following equations:

1. 2 X 3 + 4
2. 2 X (3 + 4)
A
14
Q

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

A
15
Q

Inorder traversal of an expression tree:

Print the correct parentheses for the following expression tree

A

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

16
Q

Define Postorder Traversal.

What would be it’s application?

A

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

17
Q

Postorder Taversal of BST:

Print out each node of the following tree

A

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

18
Q

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

What algorithm is it?

A

Post-order traversal

19
Q

Evaluating an expression tree with a traversal:

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

A
20
Q

How do you implement the code for a traversal?

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

A