Assigning keys to the nodes of a Binary search tree given its shape Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of the keys to the nodes unique, given its shape. What is a good $O(n)$ algorithm for assigning each node its correct key? For example, the trees with $n=3$ nodes are shown below. Even if I  removed the keys assigned to each node, I could have labeled them manually. Now, I want an algorithm for this. The motivation here is that I'm obtaining a Binary search tree through some mechanism (and the tree has the right shape), but that mechanism is labeling the nodes incorrectly. See: https://math.stackexchange.com/questions/4051677/converting-a-dyck-path-to-corresponding-binary-search-tree.
Simply assign key $i$ to the $i$-th node to appear in an in-order depth-first traversal of the BST.