external_b_tree.cc

void print_external_nodes(shared_ptr<BinaryTree> root) {
  if (!root) {
    return;
  }
  left_dfs(root->left, true);
  right_dfs(root->right, true);
  
}

void left_dfs(shared_ptr<BinaryTree> n, bool is_ext) {
  if (!n) {
    return;
  }
  
  if (is_ext || (!n->left && !n->right)) {
    cout << n->data << endl;
  }
  
  left_dfs(n->left, is_ext);
  left_dfs(n->right, is_ext && !n->left);
}

void rigt_dfs(shared_ptr<BinaryTree> n, bool is_ext) {
  if (!n) {
    return;
  }

  right_dfs(n->left, is_ext && !n->right);
  right_dfs(n->right, is_ext);
  
  if (is_ext || (!n->left && !n->right)) {
    cout << n->data << endl;
  } 
}