# 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

Graded Playground Autograder

**Activity Prompt:**

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.

`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!

#include "integer_tree.hpp"
#include <iostream>
int main() {
}

#ifndef INTEGER_TREE_HPP
#define INTEGER_TREE_HPP
#include "node.hpp"
class IntegerTree {
public:
// assigned
double AverageValue();
// provided
IntegerTree() = default;
private:
Node<int>* root_ = nullptr;
};
#endif

#include "integer_tree.hpp"
#include <stdexcept>

#ifndef NODE_HPP
#define NODE_HPP
template <typename T>
struct Node {
int value = 0; // NOLINT
Node<T>* parent = nullptr; // NOLINT
Node<T>* left = nullptr; // NOLINT
Node<T>* right = nullptr; // NOLINT
Node() = default;
Node(int value) : value(value) {}
};
#endif

Submit is not supported in this site.