gistfile1.txt

#include <vector>
#include <iostream>

struct TreeNode {
  int value;
  TreeNode *left;
  TreeNode *right;

  TreeNode(int value_): value(value_), left(nullptr), right(nullptr) {}
  ~TreeNode() { delete left; delete right; }
};

void Traverse(const TreeNode* node, std::vector<int>& target_vec) {
  if (!node) return;
  Traverse(node->left, target_vec);
  target_vec.push_back(node->value);
  Traverse(node->right, target_vec);
}

void InsertNode(TreeNode* &root, int value) {
  if (!root) {
    root = new TreeNode(value);
  } else {
    TreeNode* current_node = root;
    while (current_node) {
      if (value <= current_node->value) {
        if (current_node->left) {
          current_node = current_node->left;
        } else {
          current_node->left = new TreeNode(value);
          return;
        }
      } else {
        if (current_node->right) {
          current_node = current_node->right;
        } else {
          current_node->right = new TreeNode(value);
          return;
        }
      }
    }
  }
}

TreeNode* ConstructTree(const std::vector<int>& source_vec) {
  TreeNode* root = nullptr;
  for (auto value: source_vec) {
    InsertNode(root, value);
  }
  return root;
}

int main() {
  std::vector<int> source_vec = {4, 2, 1, 3, 5, 8, 7};
  std::vector<int> target_vec;

  TreeNode* tree = ConstructTree(source_vec);
  Traverse(tree, target_vec);
  delete tree;

  for (auto value: target_vec) { 
    std::cout << value << " ";
  }
  std::cout << std::endl;
  return 0;
}