Have you ever climbed a tree? It’s hard work, especially if it’s a tree the size of General Sherman. Not the one who decided to burn down the entire state of Georgia (climbing on top of an average-sized dead man is pretty easy if you ask us), but the largest tree in the world (by volume). Don’t bother trying to climb it. You won’t find any branches low enough to get you started, even if you manage to sneak past the park rangers.

Unless you managed to get some Geckskin shoes or something…

In cool, nature-based stick technology aside, you'll probably want to go with trees that actually have branches you can reach. Trees with reachable branches are much easier to climb. If you want to go up, you choose a higher branch. If you want to get back down, you choose a lower branch. Sounds kind-of binary, doesn't it? You have two options: going up or down.

And like that we’ve transitioned to computer science. We’re just that smooth.

Computer science may not have trees the size of General Sherman—or any living trees for that matter—but our trees make searching for data much easier, just like branches make climbing easier.

Searching with Trees

Imagine you’re in a 10,000 ft² warehouse full of random garage sale treasures. That’s 100 feet by 100 feet of

• clothes too old to be in-style and too new to be retro.
• toys so actively loved that they're practically worthless to anyone else.
• strangely large portraits of (probably) dead people giving you dirty looks.
• kitchen gadgets that you'd take more time to learn than ever use.
• space harlequin mass market mystery paperbacks.
• furniture with mysterious stains.

There's a ton of junk, but you know someone mistook your favorite pair of sneakers for clothes too old to be in-style and added them to pile.

Rude.

Whoever it is who stole mistook them knows exactly where they are, but they don't want you to find them. (Super rude.) You managed to make them play "Hot or Cold" with you. That way, it's a fair fight about what happens to the sneakers.

"Hot or Cold" sounds like a pretty arbitrary game to play, and…it is, but it's also a good way to narrow down the space you need to search quickly. Say you go spelunking through the junk alone, searching every nook and cranny for those sneaks. You could spend the next few weeks rummaging through all 10,000 ft² of off-colored t-shirts and tablets with cracked screens.

Instead, if you can get the sneak-stealer (that back-stabber) to narrow that search down to 9 ft² instead, you'll be looking at a 3 × 3 grid instead of a 100 × 100 one. Surely you can find a pair of shoes in that tiny space.

The problem is there are about 1,111 of those 3 × 3 spaces. You have to learn how to ask the right question to make it happen.

Stand in the middle of the warehouse and ask the Brutus of athletic footwear which half of the quagmire has your sneakers. There are only two possible answers (left or right).

Let’s say they tell you the left half. Just like that you’ve cut the space down to 50 × 50. Now stand in the middle of that half and ask the same question again. They tell you to take the right half. Down to 25 × 25.

You get the idea.

Do the same thing three more times and you’re down to about a 3 × 3 grid. You could have searched all 1,111 of the 3 × 3 squares, but instead you used a binary search to cut down on all that rummaging.

Set up your trees correctly, and they'll be binary-searching fiends. By making nodes that can point to two other nodes each, you can make compact data structures that self-organize by whatever you want. Then you can go down the tree and find things in much less time than a plain-old list.

Hello sneakers, we’ve missed you.

How do you create a tree? You don’t. All you can do is plant a seed or a sapling, and hope for the best. Sometimes you end up with a tree that grows four inches in 155 years, and other times you get nine feet per year. The first option's great if you want shade for your great grandkids’ ant farm. Nine feet of growth in one year sounds way better if you ask us, though. That might be fast for a tree tree, but not for a computer science tree.

Sure, programming a tree might take more time at the beginning, but you don’t have to wait as long for it to grow. If you balance it right, a binary 9 layers deep has over 1000 nodes. Add just one more layer of height and you get almost 2050.

Take that, 2048.

You aren't going to get shade, fruit, or lumber, but you will get incredibly fast searching and inserting (assuming it’s properly balanced and sorted). Finding just one node among those two thousand (or finding the right spot to insert a new node) would take, at most, only 10 tries.

Ten! Good luck doing that with a list, much less a paulownia tomentosa.

Even a huge tree with a spot for every single person on earth, you could find a single person in no more than 33 tries—assuming the tree's sorted. We’re totally serious—and you don't need witchcraft to make it happen. This storage/searching efficiency is actually the biggest reason trees are so popular, and it’s easy to program into any tree’s basic structure.

When you need to compress .mp3 and .jpeg files for your phone, trees are there. They also guide your computer through the maze of the internet, NBD. With trees, you can make your computer talk to any other connected computer so you can work on your Beyoncé lip-syncing skills from the comfort of your own couch.

They're the true heroes of the internet and computer science in general. Even compared to cats.

(Source)