Controls: Space: Reorder BST with morris traversal (2nd button) P: Pause physics and reordering (1st button) S: Step forward one command (3rd button) Click and drag: On a node: move node On the background: move camera Scroll, or up/down arrow keys: zoom camera When a node is selected: R: create right node if possible (4th button) L: create left node if possible (5th button) Z: Show program and memory arrays (6th button)
This is a visualization of a way of traversing a binary search tree. It has a runtime complexity of O(2n) and no memory overhead. To be able to pause execution of the traversal, I have implemented a low level scripting language which reads commands from commandArray and writes/reads memory from memoryArray. Documentation and the original traversal implemented in Java can be found in the background comments, and the arrays can be seen by pressing Z or the 6th button. The data structure has getter and setter methods similar to what one would expect from a binary search tree, but due to scratch not supporting object oriented data structures, the implementation differs. A single "node" is spread over 4 lists, nodeUUID, nodeValue, nodeLeft and nodeRight. nodeLeft and nodeRight store a "pointer" which is the index of the node in the list they're pointing to. nodeUUID stores a unique number, so a node can be found after it's pointer is changed due to insertion / deletion, and nodeValue stores the value displayed on that particular node. The visualization of the BST is completely separate from any BST related methods. In the implementation of the Morris Inorder Traversal algorithm, I have designated memory index 1 to store the pointer to currentNode, and memory index 7 to store the pointer to previousNode. The visualization reads directly from these addresses to display the outlines. The visualization uses a basic physics system to keep the BST untangled. Each child node is kept 100 units away from the parent, and has a force applied depending on the cloneID representing the node, and the node's y position. This works well enough for the current purposes of this project, but I'd like to revisit this later. Paper Citation: Joseph M. Morris, Traversing binary trees simply and cheaply, Information Processing Letters, Volume 9, Issue 5, 1979, Pages 197-200, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(79)90068-1 (https://www.sciencedirect.com/science/article/pii/0020019079900681) Keywords: Binary trees; tree traversal Christoph Buchheim, Michael Jünger, and Sebastian Leipert. 2002. Improving Walker's Algorithm to Run in Linear Time. In Revised Papers from the 10th International Symposium on Graph Drawing (GD '02). Springer-Verlag, Berlin, Heidelberg, 344–353.
