O1_traversal_binary_tree.cpp

// write by XiongYi
TreeLinkNode *GetNextNode(TreeLinkNode *root, int seq_req) {
  int seq_init = 1;

  while (seq_init < seq_req) {
    if (IsInLeft(seq_init, seq_req)) {
      root = root->left;
      seq_init = seq_init * 2;
    }
    else {
      root = root->right;
      seq_init = seq_init * 2 + 1;
    }

    if (!root)
      break;
  }

  return root;
}

bool IsInLeft(int seq_cur, int seq_req) {
  assert(seq_cur <= seq_req);
  
  while (seq_req <= seq_cur * 2 + 1)
    seq_req /= 2;

  return seq_req % 2 ? false : true;
}

// my update
TreeLinkNode *GetNextNode(TreeLinkNode *root, int seq_req) {
  list<bool> path;
  while (seq_req > 1) {
    path.push_front(seq_req % 2 == 1);
    seq_req /= 2;
  }
  for (list<bool>::iterator it = path.begin(); it != path.end(); ++it)
    root = (*it) ? root->right : root->left;

  return root;
}