#include <iostream>

using namespace std;

struct TNode {
  int m_nVal;
  TNode *m_pLeft;
  TNode *m_pRight;
};

TNode* ConvertNode(TNode *pNode, bool bRight) {

  if(pNode==NULL)
    return NULL;

  TNode *pLeft = NULL;
  TNode *pRight = NULL;

  if(pNode->m_pLeft)
    pLeft = ConvertNode(pNode->m_pLeft, false);

  if(pLeft) {
    pLeft->m_pRight = pNode;
    pNode->m_pLeft = pLeft;
  }

  if(pNode->m_pRight)
    pRight = ConvertNode(pNode->m_pRight, true);

  if(pRight) {
    pNode->m_pRight = pRight;
    pRight->m_pLeft = pNode;
  }

  TNode *pTMP = pNode;
  if(bRight) {
    while(pTMP->m_pLeft)
      pTMP = pTMP->m_pLeft;
  } else {
    while(pTMP->m_pRight)
      pTMP = pTMP->m_pRight;
  }

  return pTMP;
}


void Convert(TNode *pRoot) {
  
  ConvertNode(pRoot, true);
}



int main(int argc, char **argv) {

  return 0;
}