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.
2 Answers
Simply assign key $i$ to the $i$-th node to appear in an in-order depth-first traversal of the BST.
-
$\begingroup$ 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. $\endgroup$ Mar 6, 2021 at 21:17
-
1$\begingroup$ 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. $\endgroup$– StevenMar 6, 2021 at 21:21
-
$\begingroup$ In particular, the first visited node is the "leftmost" node of $T$ (which must contain the smallest key and hence it is assigned 1). $\endgroup$– StevenMar 6, 2021 at 21:30
-
-
$\begingroup$ 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. $\endgroup$ Mar 6, 2021 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.)