void traverse(TreeNode* root) {
  if (root == nullptr) return;
  traverse(root->left);
  cout << root->val << " ";
  traverse(root->right);
}