# 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.

• Your 4th tree is not a BST. – Steven Mar 6 at 21:13
• Thanks, fixed it. – Rohit Pandey Mar 6 at 21:15

Simply assign key $$i$$ to the $$i$$-th node to appear in an in-order depth-first traversal of the BST.

• Sorry, can't readily find resources for "symmetric depth first search". Where would this search begin? At the root? Then you would always assign $1$ to the root, so that can't be right. – Rohit Pandey Mar 6 at 21:17
• The symmetric (also called in-order) DFS visit of a tree $T$ can be defined recursively. If $T$ contains a single node $x$, the list of visited nodes contains only $x$ itself. If $T$ has $\ge$ 2 nodes, let $r$ be the root of $T$. The visit of $T$ is obtained by concatenating the visit performed on the subtree of $T$ rooted in the left child of $r$ (if any), with $r$, with the visit performed on the subtree of $T$ rooted in the right child of $r$ (if any). See here. – Steven Mar 6 at 21:21
• In particular, the first visited node is the "leftmost" node of $T$ (which must contain the smallest key and hence it is assigned 1). – Steven Mar 6 at 21:30
• Ok, thanks. Need to digest this. – Rohit Pandey Mar 6 at 21:32
• So this is basically in-order traversal correct? If so, might help to add that keyword to your answer since many people are more familiar with it. – Rohit Pandey Mar 6 at 21:57

Perform an inorder traversal. This can be recursively defined as "traverse left subtree, visit root, traverse right subtree".

Alternatively, follow the tree (visiting each node "between" left and right subtrees.)