Tree traversal

Question 1

Pre - order traversal

Answer 1

the value of the node is always output first before checking for nodes on the left and then for nodes on the right.

Question 2

use of pre-order traversal:

Answer 2

copying a tree
Pre-fix of an expression

Question 3

How does pre-order traversal implement a recursive algorithm?

Answer 3

it is repeatedly called until all of the nodes have been processed. The first time that the function is called, it will be passed the address (pointer) of the root node. Each time the function is called a new node will be referenced (the left or right child node), until the base case is reached.

Question 4

In - order traversal:

Answer 4

the value of the node is output after the left-hand nodes are inspected but before the right hand node is inpsected.

Question 5

Use of In-Order traversal:

Answer 5

In a binary search tree the nodes are arranged in correct order so, in-order traversal would output the nodes in correct order.
-In-fix of an expression

Question 6

Post-order traversal:

Answer 6

the value of the node is output after both the left AND the right nodes have been explored.

Question 7

use of Post-order traversal:

Answer 7

used to convert from infix to postfix notation
emptying a tree

Question 8

What is the same as post-order traversal?

Answer 8

Depth first search because it uses a stack to manage the backtracking and the nodes are processed the final time they are visited