Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Why do trees grow downward in computer science?

I have a feeling it goes back to a printer, and that a program traversing a tree first prints the root, and uses the notion of a bottomless stack of paper to express the indefinite levels of recursion that might be encountered.

References:

Trees grow downward, having their roots at the top of the page and their leaves down below

From ON HOLY WARS AND A PLEA FOR PEACE.

by convention, trees are drawn growing downwards

From the Wikipedia article on tree data structures.

Real trees grow from their root upwards to the sky, but computer-science trees grow from the root downwards

From David Schmidt's lecture notes.

share|improve this question
8  
Why are manholes round? –  Job May 16 '12 at 20:18
8  
Trees grown in all directions in nature...upward, downward, etc –  CaffGeek May 16 '12 at 20:45
7  
@Job To prevent the manhole covers from falling in. FTFY. :-) –  Gary Rowe May 16 '12 at 20:58
6  
@GaryRowe: A widely propagated falsehood. Manhole covers are round primarily because they cover ends of pipes, and pipes are round. Pipes are round because 1) that distributes stress on them evenly, and 2) it maximizes the cross-section for a given perimeter. Overall, it maximizes the strength and capacity of the pipe you can get from a specific amount of material. –  Jerry Coffin May 16 '12 at 21:10
10  
@JerryCoffin: So.... trees grow downward because round pipes are stronger than square ones? ;) –  FrustratedWithFormsDesigner May 16 '12 at 21:12

3 Answers 3

up vote 13 down vote accepted

Just a guess:

Tree structures grow downward (root at top, leaves at bottom) because people read from the top of the page toward the bottom. Furthermore, if you were to draw a large tree that spanned several pages, it would be awkward to ask the reader to skip ahead a few pages and then work backward.

Furthermore, whether the convention started for the reason explained above or for some other reason, we continue the practice today exactly because it is a convention. We have corresponding terms like top level node (meaning the root) that wouldn't make as much sense if we drew the structure with the root at the bottom.

share|improve this answer
1  
@BruceEdiger: I'm going to guess that it just comes down to different conventions. –  FrustratedWithFormsDesigner May 16 '12 at 20:33
3  
@BruceEdiger That's something quite different. The Cartesian coordinate system was established 375 years ago, so it's pretty natural to stick to that convention. Graphics systems (X11, QuickDraw, Quartz on iOS) often use a flipped coordinate system. I don't think that has anything to do with how we draw trees, though. –  Caleb May 16 '12 at 20:36
3  
IMHO the reason for the flipped coordinates dates back to the time where one had terminals. Since they displayed text beginning from the upper left corner and the actual resolution may vary, it was a very reasonable decision to make (0,0) be the upper left corner. –  FUZxxl May 16 '12 at 20:55
1  
@BruceEdiger on-screen coordinates essentially map from (x,y) to the memory location of the pixel/character. Video display controllers responsible for mapping memory to an image starts at location 0 in the upper left corner. Hence it is a natural mapping to have (0,0) there as you can get the memory location just with (y*80+x). Documentation for the 8-bit computer I learned this with: datamuseum.dk/w/images/5/5b/RC702_Tech_Man.pdf –  user1249 May 17 '12 at 7:25
2  
When drawing a tree by hand, it is hard to know how much space you will need, it is also hard to layout the notes neatly without first drawing the level above. So you tend to draw the “root” first putting it up the top so you can continue with your text where ever on the page the tree finishes. –  Ian May 17 '12 at 8:47

The convention appears to stem from the Coffman-Graham Algorithm which is designed:

"...for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W."

Their paper from 1972 (PDF) shows a directed acyclic graph being drawn from top to bottom. It is a short step to represent a tree in the same manner.

There is some further commentary on this visualisation in this article on Layered Graph Drawing.

share|improve this answer
6  
+1 for not guessing. –  Caleb May 16 '12 at 21:28
1  
The Art of Computer Programming: Fundamental Algorithms, Volume 1 – Fundamental Algorithms, was published in 1968, and had a section 2 about trees. Can someone owning this book verify that diagrams show trees growing down? If so, the history points us to a convention started even earlier. Also, I wonder if computer science picked up from mathematics this convention from even earlier than 1960. Wolfram shows trees were studied in 1857. –  maxpolk May 17 '12 at 12:28
3  
@maxpolk Knuth draws his trees in the root-at-top way in, and discusses his decision (sec. 2.3, pp. 311 in the 3rd edition) to convert form root-at-bottom form prior to publication of the first edition. It boils down to "most of the existing literature goes top-down, and we need a consistent model for discussion purposes" (80% according to Knuth's survey). –  Ross Patterson May 20 '12 at 15:57

Drawing from the top > down and left > right are popular in computer science because those are the starting directions in written English. Considering that most computer science papers are written in English regardless of the native language of the writer this would be the most prevalent way to draw diagrams.

It is most natural for an English language reader to read a graph from top > down or left > right than either of the other alternatives.

Do a search of images.google.com for directed tree graph and review the results. The only tree diagrams I could find that went up were UML Class Diagrams, and only because that is the convention that UML chose for Class Diagrams. All other UML Diagrams go left > right or up > down.

I would consider reading directed tree graphs from down > up as un-natural as reading top posted email threads; which to say is completely un-natural.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.