Binary tree challenge example

Question

I have been watching some lectures from the excellent Richard Buckland and experimenting with binary trees but I don't completely understand how to implement one. Below is how far I have got.

class Tree(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

t = Tree(4, Tree(2, Tree(1), Tree(3)), Tree(6, Tree(5), Tree(7)))

Could somebody refer me to a simple example problem which can be solved using a binary tree. I don't really understand what data I will be presented with to create the tree or how I could use it practically. I'm scared to google for some examples because I don't want somebody else's source code. I want to work out the implementation myself. But before I can do this I feel I need a problem to solve. Ideally, I would like a couple fairly trivial example problems and then a few more intermediate problems.

Answer 1

Your code above is a "valid" implementation of a binary tree... it's already complete. You have nodes (which you call Trees) and each node can have 0, 1, or 2 children. edit Actually I just realized that you can't implement an empty tree using your implementation, but that's a small nitpick.

This is a semantic thing but it's "sort of important". A binary tree by itself isn't really used for problems at all. A standard binary tree is not really useful--it's just a tree where each node has at most two children. This link should clarify what I'm saying (and probably contains a sufficient answer to your question): https://stackoverflow.com/a/2159506.

I think what you're actually interested in is a "balanced binary search tree" which has extra properties. In particular, it's "ordered" from the left to right (that's a vague description, but I don't want to be hand-wavy and say that the "left child is less than the parent and its sibling" when it could actually be equal in some implementations). It also has a O(log(n)) bounded depth (you won't have trees of height n with n objects in it... which is just a linked list).

Anyways, to answer your question: it's sort of boring, but a common suggestion is to implement an abstract data structure such as a heap or dictionary. Note the terminology: a heap can be implemented using a binary search tree. A heap, by definition, is not tied to any implementation. It only requires that certain operations can be performed on it (e.g. peek(), min(), add(), etc). Choosing a primitive data structure like a binary tree is necessary to produce a heap (otherwise it's just this abstract thing floating in your head). Choosing a balanced binary search tree also gives time complexities to those operations (e.g. a heap implemented with a balanced binary search tree has O(log(n)) peek(). See the wiki link for more details: http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants).

Once you've written a heap, you can look at any problem whose algorithm uses a heap... there's a lot. Say you want to find the kth largest element in linear time. Heap (proving this is a bit tricky though). What if you want to implement Prim's algorithm? Heap. What if you want to sort arbitrary objects with worst case O(n log(n))? Heapsort (note that usually people don't use heap sort since it's not actually fast).

Answer 2

Well, try this: http://www.spoj.com/problems/TREE/

Or this: http://www.spoj.com/problems/THREECOL/

http://www.spoj.com/problems/NWERC11B/

These problems are not trivial, and will ask time, but you will definitely learn from this.

Basically, there is a vast number of problems that essentially need binary trees in some way. For example, building an inference algorithm in propositional logic.

And yes, if you can get a hold of Sedgewick's algorithms, there are chapters about binary search trees, for example, pretty useful.