Weekly Programming Challenge #1
Implement a binary search tree
I’ve been toying with an idea. This sort of thing is hardly new, so I don’t claim it as an original idea, but I can’t shake it, so I’m going to run with it.
Here it is: each week, I will post a new programming challenge. It might be to implement a data structure or algorithm. It might be to accomplish some task (like, find a solution to some puzzle or logistics problem).
It will always be something that requires you to write some software, and you will be challenged to complete it either as described (“normal”), or with some additional, specified constraints added (“hard”), or with some wacky, made-up constraints of your own that make the solution especially notable (“surprise me”).
You’ll have a week to produce your implementation. You’ll need to share it somewhere publicly accessible (I recommend a GitHub repository for these challenges). At the end of the week, all who participated will be listed, with the corresponding honors (“normal”, “hard”, or “surprise”). I may comment on those that I think especially deserve calling out, and then we’ll go around again with a new challenge.
No prizes. No judging. No competition. Just good, old-fashioned recreational programming in which we all might learn something new, and maybe have a chance to show off. :)
Are you on board? Great! Here goes…
Binary Search Trees!
A binary tree is a collection of nodes. Each node may have exactly zero, one, or two children. Every node has exactly one parent, except for the root node, which has no parent. Here’s a binary tree, where each node contains an integer:
A binary search tree is a binary tree where the nodes are ordered so that they may be searched very efficiently. When adding something to a binary search tree, you compare the new value to the root node. If it is less than the root node, you add it as the left-hand child. If it is greater (or equal), you add it to the right-hand child. If the node already has a left- or right-hand child, add the value to that child instead, proceeding recursively until you find a place to add the value.
To search the tree, then, you simply make the root node the “current” node, and then proceed recursively: compare the value you’re searching for with the current node. If it is less than the current node, search on the left-hand child. If it is greater, search on the right-hand node. If it is equal, well then, you’ve found what you’re looking for!
The Challenge
Normal Mode: Implement a binary search tree in the language of your choice. It should:
- Be configurable to support any kind of ordered data, though you may expect the data to be homogenous. (That is to say, you don’t have to compare strings and integers in the same tree, but your tree should support comparing both strings and integers, and any other ordered kind of data.)
- Support “insert” operations (adding values to the tree, in appropriate order.)
- Support “search” operations (finding a node with a specific value).
- Optionally support “delete” operations (removing a node from the tree). This is trickier than it sounds — but if you want a bit more challenge without going full-on hard mode, feel free to give this a try!
Hard Mode: The problem is that binary search trees can degenerate into simple linked lists, especially if given data that is already sorted. The root node points to just one child, which points to just one child, which points to just one child, all the way down to the one leaf of the tree. Searching this is not optimal — to find the value at the leaf, you wind up looking at every node of the tree! How do you get around that? Self-balancing binary search trees. There are several data structures that fall into this category, including AA trees, AVL trees, and Red-Black trees. For hard mode, implement one of these, with all the same requirements as normal mode, PLUS support for delete operations.
Suprise Me! Be creative. The sky’s the limit! As long as the result has something to do with binary search trees, it can be considered for this category, but it ought to be (1) software that you’ve written, and (2) at least as challenging as hard mode.
On your mark…get set…go!
This challenge is now ended, but please feel free to post your solutions anyway! I always love to see how people approach problems like this. To see the summary of this first programming challenge, read this post.