Find if a sequence of node is a result of a binary tree preorder traversal
Idea of a tree construction

If the length of the sequence is $1$ then just make the first symbol root and stop with SUCCESS. If the first symbol of the sequence is $0$ then construction is not possible, otherwise make it the ROOT and set the root to the ROOT. 

for i = 2 to n
 if n[i] is 1 then
   if root.left is free 
     root.left = make_node(n[i])
     root = root.left #go to left
   else if root.right is free then      
     root.right = make_node(n[i])
     root = root.right #go to right
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 else if n[i] is 0 then
   if root.left is free 
     root.left = make_node(n[i])
   else if root.right is free
     root.right = make_node(n[i])  
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 end

 if root is nil then break
end

if i &lt; n the construction impossible


Checking without a tree construction

The basic idea is at each step to count how many nodes we can add to the tree. When we read $1$, we add one internal node which allows to add two new nodes and hence $-1+2 = 1$ and so we increment the counter by one. When we read $0$ we add a new leaf and so we decrement the counter.

if a[0] == 0 then 
  return FAILURE
else
  counter = 2

for i=2 to n
  if a[i] == 1 then
    counter = counter + 1 
  else
    counter = counter - 1
  end

  if counter == 0 then break  
end

if i &lt; n then 
  return FAILURE
else
  return SUCCESS
end  


Construction example

$1,1,0,1,1,0,0,1$

  1 =&gt;  1  =&gt; 1  =&gt; ... =&gt;  1
       /     /             /
      1     1             1
           / \           / \
          0   1         0   1
                           / \
                          1   1
                         / \
                        0   0


Checking example

c=2, c=3, c=2,c=3, c=4, c=3, c=2, c=3, SUCCESS

At the end c=3 means we still can add 3 leaves.