An introduction to trees

This lesson contains approximately 47 minutes of video content.

An introduction to trees

Binary trees

Trees with unbound branching

Other tree representations

Activity: Branching Tree

Graded Playground Autograder

Activity Prompt: In this activity, you will implement a BranchingTree<T>. The BranchingTree<T> type will contain a single private data member named root_ that is typed Node<T>*. We will now introduce the types involved in this assignment and what you're responsible for implementing.

Node<T>

public:
Node<T>* parent Points to a respective node's parent node in the tree structure
std::list<Node<T>*> children A list of pointers to the individual node's children
T data T data, the data stored in the node.

BranchingTree<T>

Your BranchingTree<T> implementation will define three public behaviors and one private data member:
public:
BranchingTree(const T& data) Parameterized constructor: initializes a new BranchingTree<T> object with a single node with data pointed to by root_.
const Node<T>* GetRoot() const Completed for you. Returns a pointer pointing to the tree's root node (read-only).
Node<T>* GetRoot() Completed for you. Returns a pointer pointing to the tree's root node.
private:
Node<T>* root_; Pointer to the root of the BranchingTree<T>.

Non-member helper functions

You will also define two non-member helper function templates.
Node<T>* InsertChild(Node<T>* parent, T data) If the parent's children list does not contain a node with data, inserts a new node whose data is data and parent is parent into the parent's children list; otherwise, throws an exception. Returns the address of the new node.
unsigned int FindDepth(const Node<T>* node) Returns the depth of the node in a BranchingTree<T> object. A Node<T> whose parent is nullptr has a depth of 0.

Both functions should throw an exception if the passed Node<T>* is nullptr.

How do I interact with std::list?

If you're curious about how you should interact with an std::list, consider this example: 
std::list l;
l.push_back(11);
l.push_back(12);
for (const int& i : l) {
  std::cout << i << std::endl;
}
#include <iostream> #include "branching_tree.hpp" int main() { /* Example Usage */ // BranchingTree<int> bt(11); // auto root = bt.GetRoot(); // auto node12 = InsertChild(root, 12); // auto node12_depth = FindDepth(node12); }
#ifndef BRANCHING_TREE_HPP #define BRANCHING_TREE_HPP #include "node.hpp" template<typename T> class BranchingTree { public: BranchingTree(const T& data); const Node<T>* GetRoot() const {return root_;} Node<T>* GetRoot() {return root_;} private: Node<T>* root_; }; // helper function declarations template<typename T> Node<T>* InsertChild(Node<T>* parent, T data); template<typename T> unsigned int FindDepth(const Node<T>* node); // implementations template<typename T> BranchingTree<T>::BranchingTree(const T& data) { // does something; } template<typename T> Node<T>* InsertChild(Node<T>* parent, T data) { // does something; return nullptr; } template<typename T> unsigned int FindDepth(const Node<T>* node) { // does something else; return 0; } #endif
#include "branching_tree.hpp"
#ifndef NODE_HPP #define NODE_HPP #include <list> template<typename T> struct Node { T data; Node<T>* parent = nullptr; std::list<Node<T>*> children; }; #endif

Lesson materials