Find a pre-order of some numbers with their levels in BST

Question

I have a list that, for example, is 5 digits, each digit of which has its own level in BST :

list →

 [digit :6 level:1, digit :3 level:2, digit :5 level:3, digit :2 level:3, digit:1 level:4] 

How can I find my pre-order, which is {6,3,2,1,5}?

Keep in mind that I have 10,000 digits in my list above.

thanks

Answer 1

To go through BST in preliminary order, you need 1. Visit the root (ie your number) 2. Move the left subtree. 3. Move the right subtree.

Each subtree is recursively moved in the same way (root, left and right).

In your example, you do not have a clear indication of which number is on the left or right of it. Once you get to 10,000 digits of your list, you will have many numbers on the same level (for example, level 20), and if your list is not structured better than a BST that you cannot handle.

Just saying the number: 65 is at level: 20, you did not indicate whether it is to the left of the number: 70 at level: 19 or to the right of the number: 60 at level: 19.

UPDATE (as indicated by Anil):

The position of each node in the tree can be determined by analyzing two levels above it. As described by Anil, the lowest common ancestor will determine whether the number A at level X should be to the left of the number B or the number C at level X-1, depending on whether their common parent element at level X-2 is less than or more A.

Given that the pre-order is depth, you will have to iterate over (or recursively process) through the list several times, I'm afraid. If you have no memory limits, you can first build a tree.