I Have the following question:
Let $P_n$ be the set of all balanced strings of $n$ bracket pairs.
Show that there is a bijection function when given a binary tree, returns a bracket balanced string, such that for each $n$: $$f:T_{n+1}\rightarrow P_n$$
My attempt:
$Solution.$ We define the function $f$ to have a high priority to go down left, and then right. After each left step we want add "(", and after the right step, we shall add ")". This algorithm also called: "pre-order".
Now we have left to show that she is a bijection. We want to see that the amount of possible different trees under $T_{n+1}$, equals the amount of all balanced strings of $n$ bracket pairs under $P_{n}$. Since we know that each tree in $T_{n+1}$ is different, then he has unique paths. Thus, for each tree, the algorithm gives a different result in $P_n$, so the function is a bijection.
Is what I have shown good enough for what we asked for in this question? I had a different approach to this question when I tried showing an inverse function to $f$, given that $T_n \approx \coprod\limits_{k = 1}^{n - 1} T_k \times T_{n - k}$, and this formula is almost the same as Catalan one's. I will be glad for some help in this question, see if I am on the right direction or not. Thanks!
Your description is rather vague. I think a more precise way to define it would be as follows:
Let $e$ be the non-branching binary tree, and let $br(a, b)$ be the binary tree which has left child $a$ and right child $b$. Note that $e \in T_1$, and if $a \in T_n$, $b \in T_m$, then $br(a, b) \in T_{n + m}$.
Define $f : T \to P$ as follows:
$f(e) = \epsilon$
$f(br(a, b)) = (f(a)) f(b)$
To be more precise, $f(br(a, b)) = ``(" + f(a) + ``)" + f(b)$ where $+$ is string concatenation).
Claim: for every tree $t$ with $n + 1$ leaves, $f(t)$ has $n$ pairs of brackets.
Proof: this follows immediately from structural induction on $t$.
Now, let's discuss why $f$ is a bijection. Note the following theorem:
Theorem: for all $p \in P$, exactly one of the following is true: $p$ is the empty string; or there is a unique pair $(a, b) \in P^2$ such that $p = ``(" + a + ``)" + b$.
I'll omit the proof of this theorem, but it is critical.
Now, we must show that for all $p \in P$, there is a unique $t \in T$ such that $f(t) = p$. This follows from strong induction on the length of $p$ and the above theorem.
Thus, $f$ is a bijection.