Section 8 Chapter 44 - Recursive Algorithms

Question 1

Recursion

Answer 1

An algorithm or subroutine that is defined in terms of itself

Question 2

Characteristics of a recursive algorithm (3)

Answer 2

• A stopping condition / base case that when met will return a value not determined by calling itself again
• For other input values the algorithm must call itself
• The stopping condition must be reached after a finite number of calls

Question 3

How to store a binary tree if you were gonna program with it

Answer 3

A list of records. Each record holds the left branch index, right branch index and the data

Question 4

Pseudocode for in-order traversal

Answer 4

Traverse left subtree
Visit this node (the parent of the two subtrees)
Traverse right subtree

Question 5

Pseudocode for pre-order traversal

Answer 5

Visit this node (the parent of the two subtrees)
Traverse left subtree
Traverse right subtree

Question 6

Pseudocode for post-order traversal

Answer 6

Traverse left subtree
Traverse right subtree
Visit this node (the parent of the two subtrees)

Question 7

Use of a pre order traversal

Answer 7

Copying a tree

Question 8

Use of an in order traversal

Answer 8

Outputting the contents of a binary search tree in ascending order

Question 9

Use of a post order traversal (2)

Answer 9

Converting infix to postfix (Reverse Polish Notation), emptying a tree