gotchaMinor
Why does my code work: bijecting binary trees to Dyck paths
Viewed 0 times
bijectingwhypathsdycktreesbinaryworkdoescode
Problem
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 ("up" steps) and the recurse on the tree, inserting -1's ("down" steps) based on the keys on the tree 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 ("up" steps) and the recurse on the tree, inserting -1's ("down" steps) based on the keys on the tree nodes.
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#136923, answer score: 3
Revisions (0)
No revisions yet.