I'm trying to figure the following:

Given splay tree number 1. Perform a tree traversal on it and insert each node into splay tree number 2 in that order. What type of tree traversal should be performed to obtain the same tree?

Basically, I'm not sure if there is some kind of "tree traversal" but I have a library which allows me to use the Splay tree data structure. I want to use it to "solve" exam questions where I'm asked to do a set of operations on an existing splay tree. The problem I'm trying to solve is how to obtain that existing splay tree in the first place. I guessed that if there is some special tree traversal I could use then I can recreate that same splay tree. Is there such tree traversal?

  • $\begingroup$ Fundamentally the splay tree is a deterministic algorithm. So if you insert the items in the same order you did the first time you should get the same tree. Now having said that what order would that be? Generally in a splay tree the most recently accessed items are closest to the root. $\endgroup$
    – AminM
    Feb 2 at 23:21


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.