fork download
copy 
  1. #include <cassert>
  2. #include <iostream>
  3.  
  4. struct Node {
  5.     Node(int key_, int value_)
  6.         : left(nullptr) , right(nullptr) , key(key_), value(value_)
  7.     {}
  8.     Node * left, * right;
  9.     int key, value;
  10. };
  11.  
  12.  
  13. namespace incorrect_wiki {
  14. void insert(Node* root, int key, int value) {
  15.     if (!root)
  16.         root = new Node(key, value);
  17.     else if (key < root->key)
  18.         insert(root->left, key, value);
  19.     else  // key >= root->key
  20.         insert(root->right, key, value);
  21. }
  22. }
  23.  
  24. void insert(Node*& root, int key, int value) {
  25.     if (!root)
  26.         root = new Node(key, value);
  27.     else if (key < root->key)
  28.         insert(root->left, key, value);
  29.     else  // key >= root->key
  30.         insert(root->right, key, value);
  31. }
  32.  
  33. template<typename Node, typename Callable>
  34. void visit_all(Node * root, Callable && callback) {
  35.     if (!root) return;
  36.     if (root->left) visit_all(root->left, callback);
  37.     callback(*root);
  38.     if (root->right) visit_all(root->right, callback);
  39. }
  40.  
  41. int main(int argc, const char *argv[]) {
  42.     Node * p_root{nullptr};
  43.     int keys[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
  44.     size_t const N = sizeof(keys)/sizeof(int);
  45.  
  46.     auto print_key = [](Node const & n) { std::cerr << n.key << ", "; };
  47.  
  48.     // incorrect insert
  49.     for (int i = 0; i < N; ++i) { incorrect_wiki::insert(p_root, keys[i], 1); }
  50.     visit_all(p_root, print_key);
  51.     assert(nullptr == p_root); // p_root was passed by value and nothing
  52.                                // has changed, moreover the memory allocations
  53.                                // in incorrect_wiki::insert are all leaked
  54.  
  55.     // correct insert
  56.     for (int i = 0; i < N; ++i) { insert(p_root, keys[i], 1); }
  57.     visit_all(p_root, print_key);
  58.  
  59.     return 0;
  60. }
Success #stdin #stdout #stderr 0s 3452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
1, 3, 4, 6, 7, 8, 10, 13, 14,
https://ideone.com/Dk4mTI
Demonstrate the insert code on https://e...content-available-to-author-only...a.org/wiki/Binary_search_tree is incorrect
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!