Exercises for the week 9 exercise session¶

Task 1¶

In the following exercises you will use the following rooted tree as an example. (the root of the tree is ”8”)

You have an access to a pointer to the root node.

All nodes are using the following struct:

struct Node {
  int key=NO_KEY;
  Node* parent = NO_NODE;
  std::unordered_set<Node*> children = {};
}

With the following constants:

int NO_KEY = -1;
Node* NO_NODE = nullptr;

In a rooted tree there is a unique path from each node to the root. For example, the path from the node whose key is 4 to the root is the following: { 4, 7, 6, 8 }.

Create a C++ function which compiles an unordered_set<std::deque<int>> of the paths from a node to the root node when the pointer to the root node is given.

std::unordered_set<std::deque<int>> get_paths_to_root(Node* node){
  // TODO
}

The order of the paths is irrelevant, but a single path must always be in the order from a node to the root node as in the example.

If you prefer, you can also write the answer with pseudocode.