Thoughts on the binary-search-tree exercise

So, I spent over 15 hours on this exercise before finally giving up and looking at the implementation in Github. This was my last exercise in the track and I would like to share some thoughts as a veteran programmer new to C++.

  1. Exercising the concept of a binary tree is compelling. I have a soft spot for data structure implementation in languages that I’m learning because they allow the student a good base of comparison to quickly get the feel for differences in language structure and syntax.

  2. This exercise required the user to jump into two topics that have not been introduced in any other exercise: std::unique_ptr and iterators. Yes, there’s a warning comment in the test file, but: no other exercise requires the student to really use an iterator, let alone create one. (Technically I guess we’ve used them, but we’re not conscious of the fact that they’re iterators.) I note that the only other exercise that required any sort of traversal via pointer was the simple linked lists exercise.

Conclusion: if it’s possible to split this exercise up into smaller, more manageable pieces, with each one introducing a new concept, that’d be better. As it is, after 15 hours across multiple days I gave up, marked it complete, and requested mentoring in order to figure out how the heck to implement a custom iterator using all these new concepts.

Please see if there’s a way to split this one up into multiple exercises, and if you can’t/won’t, please move it to the END of the track.

I can’t relate… but congrats on finishing the track!

I think you’re right, this is by far the most difficult exercise on the C++ track.

Not only does it force you to use std::unique_ptr, it’s also not obvious at first glance and you have to read the error messages (which are notoriously hard to read) or the tests carefully.

And the tests use a range-based for loop with the comment “The tests below require an implementation of an iterator. You can get more details here:” That page describes the iterator categories of the standard library and their syntactic and semantic requirements which is a lot to take in.

I’ve had a lot of discussions with students about these two aspects of the exercise, you’re not alone in your struggle.

I guess the intent of the original author was to enforce the use of std::unique_ptr for the left and right subtree of each node. I think that’s the right idea, the ownership of the subtrees should definitely be managed by a smart pointer. Without that explicit requirement in the tests I bet there would be a lot of solutions with owing raw pointers which is unidiomatic and dangerous.

But on the other hand having the member functions left() and right() return references to the std::unique_ptr members feels a little bit weird, most C++ programmers I know would just return (non-owning) raw pointers.

(And that invites a subtle issue where a value can be added to a subtree in a way that violates the invariant of the larger tree. That’s a tricky one.)

Maybe we could improve the exercise by either amending the instructions with a C++ specific part that explains what the solution should use std::unique_ptr and that left() and right() should return references to those members.
Or we could add the signatures of left() and right() to the initial .h file.
Or we could change the return type of left() and right() to raw pointers and add the std::unique_ptr to the initial .h file.

As for the range-based for loop and iterator: C++ is a large and complex programming language. I guess the author of this exercise saw and seized the opportunity to include these two concepts. I can understand that, they are important, they are not required in any other exercises on the C++ track, and AFAIK there’s no other exercise where they would fit naturally.

To solve this exercise you have to:

  • define a struct or class that acts as some sort of iterator (I’ll call it iterator from here on.)
  • define an operator* that returns the data of the current node.
  • define an operator++() that “increments” the iterator so that it refers to the next node
  • define an operator!= that compares two iterator and returns false iff they refer to the same node.
  • define a function begin() that returns an iterator which refers to the leftmost node in the tree
  • define a function end() that returns an iterator which represents the end of the tree

Maybe we could amend the instructions with a C++-specific explanation

(Almost?) all practice exercise here on Exercism start with a language-agnostic description of the task and some tests that specify the required output for a given input or sequence of operations.
I’m not a fan of breaking with that tradition and introducing C++-specific practice exercises that are tailored to a single concept in C++.
But maybe somebody else here has an idea.

1 Like

Thank you for your thoughtful and candid response.

Not only does it force you to use std::unique_ptr , it’s also not obvious at first glance and you have to read the error messages (which are notoriously hard to read) or the tests carefully.

This took literally several hours of googling and trying to understand what the heck was going on. It’s one thing if you know that there’s such a thing as a std::unique_ptr and that’s what you need; it’s another to look at that completely obtuse error message and say, “I’m using a pointer! What else does it want?”

Also, you’re not really using std::unique_ptrs here - you’ve actually got to use references to them because even with std::move things won’t work. There’s no intelligible resource I could find to tell me why things didn’t work, though, so it was basically shotgunning different combinations of const, *, and & until things compiled.

To be perfectly frank, by the time I figured out the basics - and I really think my “plain old pointer” solution would’ve worked - it worked on my own test code, so it does implement the API for the binary tree (minus the iterator) - I was so fed up that I didn’t even try to understand how to create an iterator.

The C++ track is amazingly good. It’s just a bit of a shame that this one exercise was so darn difficult. It certainly shook my confidence - both in my understanding of the language AND my understanding of the data structure (in which I have probably 2 decades of experience both using and teaching). “Why should it be so hard to create a binary search tree? Have I forgotten the basics?”

Adding some “warm-up” exercises that separately introduce the concepts of these new-fangled pointer types and iterators might be a good approach, even though it’s probably a lot of work. I would assess that I still don’t really understand C++ iterators and it would be fantastic if I could gain that understanding on this amazing platform.

Just some comments from a recent student.

Oh, also - it’s the only exercise to use templates (which of course means that all the code has to live in the header).

How about the simple-linked-lists exercise? That one screams “iterator” to me.

Hey there!

congratulations on solving all the exercises! That is quite the achievement. There will be more. Promise.

Ha! I feel that. That sound exactly like my “solutions” on various C++ training sites.

Great to hear that! A lot of that comes from the excellent mentors we have on the track.

You are basically describing the goal of the syllabus. I am actively working on it as we speak. It will have a unit about raw pointers and also one about smart pointers. There is also a concept for for-each-loops and one for iterators in the works.

Apart from the concepts, I planned to have two different linked-list exercises. One is already published - it demonstrated raw pointers.
Another would be the double linked list, that has smart pointers, templates and I also planned iterators.

Speaking about the difficulty of the trinity with you, I have to rethink that approach and maybe reduce it a bit.

I have only eight concepts that have their special concept exercises ready yet (only maintainers can see them, as they are tagged wip):


There will be more, it is just a lot of work to do on the side with a day job and social life. I have discussed my plans for the tree here and here. These are not completely up-to-date, but they show what will be in store to make the track a bit easier to complete.


I read your plans and am super excited about them. Thank you for all the effort you’re putting into making this track even better! If I can help provide a neophyte C++er’s perspective as you’re developing content, please let me know. I’m not yet good enough to mentor, but perhaps you can put my inexperience with the language to use this way.

1 Like

it’s another to look at that completely obtuse error message and say, “I’m using a pointer! What else does it want?”

I was in this exact place when I was last working on my solution to this problem. Planning to pick it back up soon. It is a challenge.