one back down. It requires enough scratch memory to store the path from the query node to the root (in the above pseudocode, the path is implicitly represented using the call stack). This can be decreased to a constant amount of memory by performing both passes in the same direction. The constant memory implementation walks from the query node to the root twice, once to find the root and once to update pointers: function Find(x) is root := x while root.parent ≠ root do root := root.parent end while while x.parent ≠ root do parent := x.parent x.parent := root x := parent end while return root end function Tarjan and Van Leeuwen also developed one-pass Find algorithms that retain the same worst-case complexity but are more efficient in practice. These are called path splitting and path halving. Both of these update the parent pointers of nodes on the path between the query node and the root. Path splitting replaces every parent pointer on that path by a pointer to the node's grandparent: function Find(x) is while x.parent ≠ x do (x, x.parent) := (x.parent, x.parent.parent) end while return x end function Path halving works similarly but replaces only every other parent pointer: function Find(x) is while x.parent ≠ x do x.parent := x.parent.parent x := x.parent end while return x end function Merging two sets The operation Union(x, y) replaces the set containing and the set containing with their union. Union first uses Find to determine the roots of the trees containing and . If the roots are the same, there is nothing more to do. Otherwise, the two trees must be merged. This is done by either setting the parent pointer of 's root to 's, or setting the parent pointer of 's root to 's. The choice of which node becomes the parent has consequences for the complexity of future operations on the tree. If it is done carelessly, trees can become excessively tall. For example, suppose that Union always made the tree containing a subtree of the tree containing . Begin with a forest that has just been initialized with elements and execute , , ..., . The resulting forest contains a single tree whose root is , and the path from 1 to passes through every node in the tree. For this forest, the time to run Find(1) is . In an efficient implementation, tree