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

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

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\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$
    – Rohit Pandey
    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$
    – Steven
    Mar 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$
    – Steven
    Mar 6, 2021 at 21:30
  • $\begingroup$ Ok, thanks. Need to digest this. $\endgroup$
    – Rohit Pandey
    Mar 6, 2021 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$
    – Rohit Pandey
    Mar 6, 2021 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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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