# 1666. Change the Root of a Binary Tree

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: Node* flipBinaryTree(Node* root, Node* leaf) { return reroot(root, leaf, nullptr); } private: Node* reroot(Node* root, Node* node, Node* newParent) { Node* oldParent = node->parent; node->parent = newParent; // clean up the child if it's the new parent if (node->left == newParent) node->left = nullptr; if (node->right == newParent) node->right = nullptr; // we meet the original root, so we're done if (node == root) return node; if (node->left) node->right = node->left; node->left = reroot(root, oldParent, node); return node; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public Node flipBinaryTree(Node root, Node leaf) { return reroot(root, leaf, null); } private Node reroot(Node root, Node node, Node newParent) { Node oldParent = node.parent; node.parent = newParent; // clean up the child if it's the new parent if (node.left == newParent) node.left = null; if (node.right == newParent) node.right = null; // we meet the original root, so we're done if (node == root) return node; if (node.left != null) node.right = node.left; node.left = reroot(root, oldParent, node); return node; } }