Since you know the node
x
will eventually become the root, maintain a tree of nodes to the left of
x
and a tree of nodes to the right of
x
, which will eventually become the two children of
x
.