Lost BSTs P20613
The binary search tree (BST) is one of the most important data structures. Remember that the fundamental property of a BST is that every subtree is such that the elements in its left child are strictly smaller than the element in the root, and the elements in its right child are strictly larger than the element in the root. Below we can see an example of BST of strings, where every key shows its level between parentheses.
| [levelsep=40pt,treesep=25pt] fly (1) box (2) at (3) dog (3) cat (4) dot (4) go (2) it (3) hi (4) |
Given all the pairs of string and level, in any order, can you reconstruct the tree?
Input
Input consists of several cases. Every case begins with the number of nodes n, followed by n pairs (string, level). Assume 1 ≤ n ≤ 104, that each string has between one and five lowercase letters, and that the given information defines a correct BST.
Output
For every case, print the preorder of the BST. Print ‘-’ for every empty subtree. Print a line with 10 dashes at the end of every case.
Input
2 hello 1 bye 2 2 hello 2 bye 1 9 box 2 dot 4 dog 3 cat 4 hi 4 fly 1 at 3 it 3 go 2
Output
hello bye - - - ---------- bye - hello - - ---------- fly box at - - dog cat - - dot - - go - it hi - - - ----------
- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++
- User solutions
- C++