as we mentioned abovebefore the reassembly at the end of the splayheader left and header right point to the roots of and lrespectively (this is not typo--follow the linksexcept for this detailthe code is relatively straightforward figure shows the method to insert an item into tree new node is allocated (if necessary)and if the tree is emptya one-node tree is created otherwisewe splay root around the inserted value if the data in the new root is equal to xwe have void insertconst comparable static binarynode *newnode nullptrifnewnode =nullptr newnode new binarynodenewnode->element xifroot =nullnode newnode->left newnode->right nullnoderoot newnodeelse splayxroot )ifx element newnode->left root->leftnewnode->right rootroot->left nullnoderoot newnodeelse ifroot->element newnode->right root->rightnewnode->left rootroot->right nullnoderoot newnodeelse returnnewnode nullptr/so next insert will call new figure top-down splay tree insert