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.