Bob and BST Permutations

Alice has recently taken a fascination for zigzag shaped trees. A zigzag tree is a binary tree where each node has at most one child and the child type alternates(i.e., a node which is a left child of its parent can have only a right child and a node which is a right child of its parent can only have a left child). The root can have either the left or the right child. You can see this from figure