Convert a min-first BST to a max-first BST

convert_min_first_to_max_first.cpp

#include <my_epi/common.h>

template <typename T>
struct BTNode {
  T data;
  shared_ptr<BTNode<T>> left, right;
};

typedef BTNode<int> NodeType;

typedef shared_ptr<NodeType> NodePtr;

void PrintPreorder(const NodePtr& root) {
  if (!root) {
    cout << "nullptr ";
    return;
  }

  cout << root->data << ' ';
  PrintPreorder(root->left);
  PrintPreorder(root->right);
}

NodePtr MakeBST() {
  //        1
  //    2       5
  //  3   4  6    8
  //          7  9 10
  auto tree = shared_ptr<BTNode<int>>(new BTNode<int> {1});
  tree->left = shared_ptr<BTNode<int>>(new BTNode<int> {2});
  tree->left->left =
    shared_ptr<BTNode<int>>(new BTNode<int> {3});
  tree->left->right =
    shared_ptr<BTNode<int>>(new BTNode<int> {4});
  tree->right = shared_ptr<BTNode<int>>(new BTNode<int> {5});
  tree->right->left =
    shared_ptr<BTNode<int>>(new BTNode<int> {6});
  tree->right->left->right =
    shared_ptr<BTNode<int>>(new BTNode<int> {7});
  tree->right->right =
    shared_ptr<BTNode<int>>(new BTNode<int> {8});
  tree->right->right->left =
    shared_ptr<BTNode<int>>(new BTNode<int> {9});
  tree->right->right->right =
    shared_ptr<BTNode<int>>(new BTNode<int> {10});
  return tree;
}

void Rearrange(NodePtr root) {
  if (!root) return;

  // rearrange the tree
  if (root->left && root->right) {
    swap(root->data, root->right->data);
    swap(root->left->data, root->right->data);
  } else if (root->left) {
    swap(root->data, root->left->data);
  } else if (root->right) {
    swap(root->data, root->right->data);
  }
  Rearrange(root->left);
  Rearrange(root->right);
}

void ConvertMinFirstBSTToMaxFirstBST(NodePtr root) {
  if (!root)
    return;

  ConvertMinFirstBSTToMaxFirstBST(root->left);
  ConvertMinFirstBSTToMaxFirstBST(root->right);

  Rearrange(root);
}

int main(int argc, char* argv[]) {
  shared_ptr<NodeType> root = MakeBST();
  PrintPreorder(root);
  ConvertMinFirstBSTToMaxFirstBST(root);
  cout << endl;
  PrintPreorder(root);

  return 0;
}