0
$\begingroup$

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.

enter image description here

$\endgroup$
2
  • $\begingroup$ Your 4th tree is not a BST. $\endgroup$
    – Steven
    Mar 6 at 21:13
  • $\begingroup$ Thanks, fixed it. $\endgroup$ Mar 6 at 21:15
2
$\begingroup$

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

$\endgroup$
5
  • $\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 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$
    – Steven
    Mar 6 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$
    – Steven
    Mar 6 at 21:30
  • $\begingroup$ Ok, thanks. Need to digest this. $\endgroup$ Mar 6 at 21:32
  • $\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 at 21:57
1
$\begingroup$

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

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.