Construct non-binary tree from pre-order traversal

Before feeding you the code to solve your problem I'd like to play a thought game with you. Take a look at the following image which represents how recursions should unroll for your input

Study the image and notice how recursions are only started when there are children for a specific node (and that they last for the number of children indicated in the input).

Try to come up with a code (or a pseudocode) on paper.

The code to solve this it is pretty straightforward: use a vector<Node> to store your children

#include <iostream>
#include <vector>
using namespace std;

struct Node {
  Node(int v) : val(v) {}
  int val;
  vector<Node*> children;
};

Node *readTreeNode() {
  int val, children;
  cin >> val >> children;
  Node *node = new Node(val);
  for (int i = 0; i<children; ++i)
    node->children.push_back(readTreeNode());
  return node;
}

int main() {
  Node *root = readTreeNode();
  // Do the cleanup..
  return 0;
}

Live Example

Notice the loop where the readTreeNode() function is recursively called

for (int i = 0; i<children; ++i)
    node->children.push_back(readTreeNode());

inner children are processed before the others.

Final caveats:

1. I didn't implement memory handling (the code above leaks memory). Be a good citizen and free your allocated memory or, even better, use smart pointers.

2. There's no error handling (i.e. no check for input nodes effectively being entered)