Lost BSTs P20613


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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
    -
    -
    -
    ----------
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++
    User solutions
    C++