fig splay tree example inserting new value into binary search tree without recursion is possible using while loop the while loop moves from the root of the tree to the leaf node which will become the new node' parent at which point the loop terminatesthe new node is createdand the parent is hooked up to its new child after inserting the new nodeit must be splayed to the top to splay it is necessary to know the path that was taken through the tree to the newly inserted node this path can be recorded using stack as the insert loop passes through another node in the treeit is pushed onto the stack the end result is that all nodesfrom the root to the new childon the path to the new child are pushed onto this path stack finallysplaying can occur by emptying this path stack first the child is popped from the stack thenthe rest of the stack is emptied as follows if two more nodes are available on the stack they are the parent and grandparent of the newly inserted node in that case double rotate can be performed resulting in the root of the newly rotated subtree being the newly inserted node which double rotation is required can be determined from the values of the grandparentparentand child if only one node remains on the stack it is the parent of the newly inserted node single rotation will bring the newly inserted node to the root of the splay tree implementing splay in the manner described here works well when looking up value in the treewhether it is found or not when value is found it will be added to the path stack when value is not foundthe parent should be splayed to the topwhich naturally occurs when the looked up value is not found because the parent will be left on the top of the path stack when splaying is performed this copy belongs to 'acha