Today we look at a few more coding problems. Yesterday we said the traversal orders can be used to serialize the tree. If we are given a preorder traveral of a tree, can we verify that the tree is serialized without reconstructing? This means it can be linear in time complexity.
Let us take an example:
    9
 3    2
4 1 # 6
is serialized as 9,3,4,#,#,1,#,#,2,#,6,#,#

Note that we can remove the right most vertices if it has two null leaves and substitute it with null.
If this is mot the case then the parent has a left subtree and we start to do the same with the left sub tree until finally there is only one node remaining and it is null.

bool IsValidBT(List<Node> nodes)
{
bool isValid = false;
  int i = Nodes.Count-1;
  while (i >= 3)
  {
      if (Nodes[i] == null  && Nodes[i-1] == null  && Nodes[i-2] != null){
         nodes.RemoveRange(i-2, 3);
         nodes.Insert(i-2, null);
        i = i - 3;
        continue;
      }
      if(Nodes[i] != null){
          if (Nodes[i+1] == null  && Nodes[i+2] == null){
           nodes.RemoveRange(i, 3);
           nodes.Insert(i, null);
          }
          i=i-1;
        continue;
      }
     i = i -1;
  }
  if (i ==0 && nodes[i] == null) isValid = true;
  return isValid;
}

If we have a binary search tree and we have an inorder and preorder traversals,
then the two traversals can be used to simultaneously find the left and right subtree length of each node.