CODEWITHSUNDEEP
c++tree
yzil
yzil

Reputation: 41

Construct non-binary tree from pre-order traversal

Given a list of nodes and the number of children it has, construct a (non-binary) tree from this list (which is in pre-order traversal)

for example I am given the following:

1 3
2 1
3 0
4 0
5 0

which is a tree that looks like

           1
          /|\
         / | \
        2  4  5
       /
      3

I know I should use recursion to construct this tree, but because it's not a binary tree, I'm pretty lost as to how this algorithm should be implemented.

Upvotes: 2

Views: 1909

Answers (1)

Marco A.
Marco A.

Reputation: 43662

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

enter image description here

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)

Upvotes: 3

Related Questions