PROBLEM LINK:
Author: Kunal Khanna
Editorialist: Lalit Kundu
DIFFICULTY:
Cakewalk
PROBLEM:
Consider N distinct elements A_1, A_2, ..., A_N. A zig-zag 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.
In how many ways can we put these N values in a zig-zag tree such that this binary tree is also a binary search tree?
EXPLANATION:
================
For each of the following two orientations, there is a unique way to fill the tree.
Consider left orientation, value on first node is smallest, then value on next node is largest of the remaining, then value on next node is smallest of remaining and so on. So, you can observe that there is only one way to fill the orientations.
So, answer is always 2, except the case when N = 1, where answer is 1.