[x0x0]

Well, to pick on Valeri, this is simply wrong

   Trees are the single most important data structure in computer science. Just 
   about everything you do in your programming career will be related to trees.

Trees are a horrid data structure for any modern processor. Pointer chasing thrashes caches. The actual most important data structure is a hashmap. The same speed in theory, much faster in practice.

[nostrademons]

This depends a lot on data size & shape. There've been some applications where I benchmarked a std::map (a tree, in practice) against Google's highly-tuned hashmap for a small (~25-50 item) container and the tree came out ahead. For such a small data structure, everything fit in L1 cache, and comparisons to follow pointers could usually be resolved by looking at the first word of the key.

One thing often forgotten with hashmaps is that they aren't actually O(1); they're O(k), where k is the length of the key, and often need to examine the entire key to derive a hashcode. This oftentimes makes them significantly slower than a binary search tree when the size of the key is large compared to the size of the container.

As always, measure before optimizing. YMMV.

[pessimizer]

Everything in programming is trees. If you write a program that calls functions, that call other functions, that's a tree.

[dalke]

I believe continuation-passing style is an alternative to the direct style you mention. Return-oriented programming and threaded programming may be specific counter-examples.

[cjhopman]

Unlikely. Unless a single function corresponds to a possibly infinite set of nodes, most programs are not trees.

[pessimizer]

A single node is a tree. main() is a tree.

[sklogic]

You do not need to represent a binary tree as a structure with two pointers. See how a typical Huffan tree is implemented, for example.

[aidenn0]

How do you represent hierarchical data in a single hashmap?

[KingMob]

Depending on your problem domain, you might be able to flatten it by just combining keys together (subject to keys being combinable like with string concatenation, using separators to ensure uniqueness of combined keys, etc.)

E.g., turn {"foo": {"bar": "moop"}} into {"foo-bar": "moop"}. This also requires writing accessor fns, but it might be worth it, depending.

[aidenn0]

Right, that works fine so long as you only ever go up the hierarchy, but going down the hierarchy would require a prefix search, which is the one place where trees actually do win over hashes.

[JBReefer]

You can frequently buy a performance increase by representing nested calculation logic in hashmaps via memoization.