# BST traversals

This lesson contains approximately 20 minutes of video content.

### Inorder traversal

Correction: In this video, `Node<T>*` objects should have been typed `BinaryTreeNode<T1,T2>*`. Also, return type of `InorderTreeWalk` should be `void` in this example. Sorry y'all!

### Preorder traversal

Correction: In this video, `Node<T>*` objects should have been typed `BinaryTreeNode<T1,T2>*`. Also, return type of `PreorderTreeWalk` should be `void` in this example. Sorry y'all!

### Postorder traversal

Correction: In this video, `Node<T>*` objects should have been typed `BinaryTreeNode<T1,T2>*`. Also, return type of `PostorderTreeWalk` should be `void` in this example. Sorry y'all!

#### Activity: Compute the average of integer values contained in a binary search tree

In this activity, you will implement an algorithm that computes the average integer value stored in the nodes of an `IntegerTree`. We have defined `IntegerTree` as non-templated Binary Search Tree that stores integer data in `Node<int>`s.
We have provided to you a basic class definition for `IntegerTree` and the class template `Node<T>`. You will find definitions for these types in the relevant files in your workspace. Here is the public member function of `IntegerTree` that you're required to define:
 `double AverageValue();` This behavior returns the average (arithmetic mean) of the values stored in the nodes of an `IntegerTree`. To compute the average, you'll need to accumulate the node `value`s and divide that total by the number of nodes in the tree. You're encouraged to define helper function(s) that are invoked by `AverageValue` to perform this computation; you can solve this problem iteratively (with an std::stack) or recursively. A recursive implementation is recommended. If the tree is empty, throw an exception.
We will only transmit the contents of your `integer_tree.hpp` and `integer_tree.cc` files to the grader. Let's get started!