Why does my code work: bijecting binary trees to Dyck paths The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan numbers. Another set of objects that follows the Catalan numbers is the number of binary search trees with $n$ nodes.
This suggests we can biject binary trees to Dyck paths (see here). We get a hint on how to do the bijection based on why the two objects satisfy the same recurrence (for Catalan numbers):
$$C_{n+1} = \sum\limits_{j=0}^{n}C_{j}C_{n-j}$$
Binary trees satisfy it because you designate one node as the root, then create a binary tree on its left (with $j$ nodes) and another one on its right. Dyck paths satisfy it by conditioning on the first time the path hits the y=0 line (which is what $j$ in the equation above represents). So we first take a mandatory step up, then we make a path of $2j$ steps that doesn't cross the $y=1$ line; then we go down one step to touch $y=0$ for the first time, and finally we make another path of $2(n-j)$ steps that doesn't cross the $y=0$ line.
This suggests we might be able to construct a Dyck path given a binary search tree (with node-keys labelled from $1$ to $n$ and there is just one way to assign them, see here) recursively, starting at the root. When we go to the left node of the tree, we need to consider the sub-path one level above the current level (where we start at level-0) and when we go to the right, we simply stay at the same level. Since the key of the node we're processing tells us where the path first struck the current level from the start, we know that it 2 times the number of steps representing the key from the start must be a step down.
The Python code below demonstrates this idea and works (tested it extensively). If you don't use python, the idea is very simple; I just set the path array to all 1's (&quot;up&quot; steps) and the recurse on the tree, inserting -1's (&quot;down&quot; steps) based on the keys on the tree nodes.
import numpy as np

class TreeToDyck():
  def __init__(self, tree_node, n):
    # Initially create an array of 2n ones. All steps are set to &quot;up&quot;.
    self.path = np.ones(2*n)
    # Now insert downs at appropriate places.
    self.tree_to_dyck(tree_node, 1)

  def tree_to_dyck(self, tree_node, start):
    if tree_node is None:
        return
    # Go down. Bear in mind the &quot;path&quot; array is 0-indexed.
    self.path[start+2*tree_node.key-2] = -1
    self.tree_to_dyck(tree_node.left, start+1)
    self.tree_to_dyck(tree_node.right, start)

Now, the thing to note is that the key of the node we're at gives us many hints about the path. But, I ignore most of them and simply insert a &quot;down&quot; step. I start with all steps in the path array set to go up. Then, based on the keys of the tree nodes, I insert down steps.
Surprisingly, this is enough. Which means the following two statements must be true:

The down steps will never collide with each other. So, we'll never insert a &quot;down&quot; step at the same location twice. This will ensure we insert $n$ down steps, as the path must contain.
The last step in the Dyck path is always a &quot;down&quot; step. So, we will always end up inserting a &quot;down&quot; at the very last position in the array no matter the tree.

I want help proving the above two statements. And if there is any other requirement needed to prove that the algorithm will work.
My answer is not a formal proof, but I hope it contains enough information to make you feel confident about your own solution. My strings start at $1$. Sorry, old habit.
Consider a binary tree $T$ with $n$ nodes. Assume $T$ has $n$ nodes, subtrees $T_\ell$ and $T_r$. If the root of $T$ has label $k$ this means that $T_\ell$ has $k-1$ nodes.
A tree with $n$ nodes has a Dyck codes of length $2n$. There are two ways of determining the Dyck code $dyck(T)$ of tree $T$. One is recursively:
$dyck(T) = U \; dyck(T_\ell) \; D \; dyck(T_r)$.
In this string we observe exactly one $D$, which is associated to the tree $T$, other $D$'s are written recursively. The position of this single $D$ is exactly at $2k$. We know this because the length of $dyck(T_\ell)$ equals $2(k-1)$.
Note that the symbols generated by $dyck(T_\ell)$ are shifted by one, because of the $U$ that is written before its code. This is the main observation: it is due to a left branch, and those left branches is what you are counting in your code.
The other way of determining $dyck(T)$ is graphical. Draw the tree and make a traversal around it. Write $D$ for a left child (even when that leads to an empty subtree) and $U$ for a right child. (We visit each node twice: this is both an pre-order and inorder-traversal.) If you try this you will see that each $D$ appears at the number of the node plus the number of times we went left as seen from the root.
The tree below has code (with subscripts that count position in the string and superscript which is the inorder label associated to the root of the corresponding subtree) $U_1^3 U_2^1 D_3^1 U_4^2 D_5^2 D_6^3 U_7^{10} U_8^6 U_9^4 D_{10}^4 U_{11}^5 D_{12}^5 D_{13}^6 U_{14}^8 U_{15}^7 D_{16}^7 D_{17}^8 U_{18}^9 D_{19}^9 D_{20}^{10} U_{21}^{11} D_{22}^{11}$.