# Tree Traversals Flashcards

What is the definition of a tree traversal?

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

What are the 3 standard ways to traverse a tree?

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

- preorder
- postorder
- inorder

Define a preorder traversal?

What is another name?

When would you use one?

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)

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

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

Define depth of a node

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

- What is the depth of the root?
- What is the depth of the child of the root?
- What is the depth of the grandchild of the root?

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
- 2
- 3

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

Pre-Order Traversal: Computing Node Depths

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

Pre-Order Traversal: Computing Node Depths

Draw the recursive call map for the following tree

Define an inorder traversal

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

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

Define an Expression Tree and describe how it works:

**How it works:**

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

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

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

What is the corresponding expression trees to the following equations:

- 2 X 3 + 4
- 2 X (3 + 4)

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

Inorder traversal of an expression tree:

Print the correct parentheses for the following expression tree

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