fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4.  
  5. struct ty_tree {
  6. 	ty_tree *left,*right; 
  7. 	int value; 
  8. };
  9.  
  10. bool foobar (ty_tree *tree, int value, int & count) {
  11.     if (tree !=nullptr) { // nullptr!!!
  12.         if (tree->value != value) {
  13.             count++;
  14.             if (foobar (tree->left, value, count) ||
  15.                   foobar (tree->right, value, count) ) // if found below
  16.             cout << tree->value<<endl;  // print the node, becaus it's on the path          
  17.         }
  18.         else {
  19.             cout << "Found: "<< tree->value<<endl;  // print the value found
  20.             return true;     // and inform caller that he can print as well.
  21.         }
  22.     } 
  23.     else return false;  // reached a leaf without finding
  24. } 
  25.  
  26. void print(ty_tree* t, int level=0) {
  27.    if (t) {
  28.    	   cout << setw(level*2)<<" "<<t->value<<endl;
  29.    	   print (t->left, level+1);
  30.    	   print (t->right,level+1); 
  31.    }
  32.    else cout << setw(level*2)<<" "<<"X"<<endl;
  33. }
  34.  
  35. int main() {
  36. 	//quik & dirty init to reproduce case
  37. 	ty_tree node[7];
  38. 	for (int i=0; i<7; i++) { 
  39. 		node[i].value =i*10; 
  40. 		node[i].left=node[i].right=nullptr;
  41. 	}
  42. 	node[1].right = &node[6]; 
  43. 	node[1].left = &node[2];
  44. 	node[2].right= &node[3];
  45. 	node[2].left =  &node[5];
  46. 	node[3].right = &node[4];
  47.  
  48. 	// check test case
  49. 	cout << "Test tree:"<<endl; 
  50. 	print (&node[1]);
  51. 	cout <<endl; 
  52.  
  53. 	// test 
  54. 	cout << "Search 40"<<endl; 
  55. 	int count=0; 
  56. 	if (!foobar(&node[1], 40, count)) 
  57. 	   cout << "not found" <<endl; 
  58.     cout << "Nodes traversed: " <<count<<endl; 
  59.  
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test tree:
 10
  20
    50
      X
      X
    30
      X
      40
        X
        X
  60
    X
    X

Search 40
Found: 40
30
20
10
Nodes traversed: 4
https://ideone.com/nJmZEL
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!