Construct a full binary tree from a pre-order list of marked nodes

Question: construct a full binary tree from a list of nodes in pre-order. The nodes are marked 'i' if they are inner nodes and are marked 'l' if they are leaf nodes.

Example given a list of nodes marked as (i, i, i, l, l, i, l, l, i, l, l), we need to construct a tree from those nodes so that the result looks like this:

Notice how all "l" nodes are leaf nodes and "i" nodes are inner nodes? Moreover, since the nodes are given in pre-order, we must take into account the node order when we put them into the tree. The first node in the list will always be the root node because in pre-order, root node comes first then left most and then right most. Also, since this is a full binary tree, we know that every node, except leaf node, must have 2 children.

With the information provided by the question, here is the code to solve this problem:

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

struct Node
{
  Node* left;
  Node* right;
  char mark;
};

Node* constructFromPreorder(Node* preorder[], int treeSize)
{
  stack<Node*> stackOfNodes;

  Node* root = preorder[0]; //pointer to root node
  
  stackOfNodes.push(preorder[0]);

  int count = 1;
  
  while (count < treeSize && !stackOfNodes.empty())
  {
    if (stackOfNodes.top()->left == NULL || stackOfNodes.top()->right == NULL)
    {
      Node* currentNode = preorder[count];
      
      if (stackOfNodes.top()->left == NULL)
        stackOfNodes.top()->left = currentNode;
      else if (stackOfNodes.top()->right == NULL)
        stackOfNodes.top()->right = currentNode;

      if (currentNode->mark == 'i')
        stackOfNodes.push(currentNode);
        
      count++;
    }
    else
    {
      stackOfNodes.pop();
    }
  }

  return root;
}

Explanation: assuming that we have the Node struct like the one in the code, then the left pointer of a node points to the left child of that node while the right pointer points to the right child. Hence, we can now put those nodes in a tree by connecting parent nodes to child nodes.

1. Declare a stack to keep track of inner nodes. Whenever we encounter an inner node, we'll push it into the stack. And, we'll pop it when it has two children. This makes sure that every inner node is connected to its two children.
2. Add the root which is the first node in the list into the stack. Because we'll add and push the nodes until the stack is empty or until we run out of nodes, we need to add the root to initialize the stack.
3. Set a count flag to 1. This count flag is used to exit the loop. When count reaches the total number of nodes in the list, it means we've run out of nodes to add into our tree. Moreover, we initialize the flag to 1 since we have already processed one node(root node) from the list in step 2.
4. Loop until either we run out of nodes to add or until the stack is empty.
5. For every loop:
   
   a) If the top of the stack is not connected to its two children yet, we get a node out of our list and attach it to the top node in the stack as that node's child. Then, we push that newly retrieved node into the stack if it is an inner node. We also increase the count flag by 1, so we can retrieve the next node in the list in the next loop.
   
   b) If the top of the stack has already been connected to two children, we pop it and do nothing.
   
   
6. When the loop is done, we simply return the pointer to the root. Whichever function uses this pointer will have access to the entire tree that we have just constructed.

Performance: this algorithm has time complexity of O(n) where n is the number of nodes in the list because we loop through the list only once. In terms of space, the algorithm has space complexity of O(m) where m is the depth of the tree we have to construct. The reason is that in the worst case we must store the second-deepest nodes into our stack.

If you have better solution or any suggestion, please feel free to leave it in the comment below. It'll be greatly appreciated :)