Why do trees grow downward?

Question

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.

Why do trees grow upward in nature? I mean, it's just a word, a 'name' that suggests *some* similarity between a new thing and an old thing we know. Don't get caught up in words :D — Phil, May 16 '12 at 20:39
Trees grown in all directions in nature...upward, downward, etc — CaffGeek, May 16 '12 at 20:45
@Job To prevent the manhole covers from falling in. FTFY. :-) — Gary, May 16 '12 at 20:58
@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
@JerryCoffin: So.... trees grow downward because round pipes are stronger than square ones? ;) — FrustratedWithFormsDesigner, May 16 '12 at 21:12
@JerryCoffin Lots more info on the subject of manhole cover design here: http://en.wikipedia.org/wiki/Manhole_cover (good call out though) — Gary, May 16 '12 at 21:15
@Job if you get the answer to that, ask: why does one park in a driveway, and drive in a parkway? — anon, May 17 '12 at 22:27
I'll note that different domains have different conventions. Abstract syntax trees are almost always drawn with operators higher on the page than operands; Bayesian network diagrams by convention make operators the *children* of operands and draw them lower on the page. — Eric Lippert, Dec 07 '22 at 22:42

score 17 · Answer 1 · answered May 16 '12 at 20:57

17

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.

answered May 16 '12 at 20:57

Gary

24,420
9
63
108

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](http://mathworld.wolfram.com/Tree.html) 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

Caleb · Accepted Answer · 2012-05-16T20:19:46.687

14

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.

edited May 16 '12 at 20:19

answered May 16 '12 at 20:14

Caleb

38,959
8
94
152

1

I'm not sure I buy this: in printed X-Y graphs, Y almost universally increases up the page. In X11 on-screen coordinates, the upper LHS of the screen is (0, 0) and Y increases down. Why don't printed X-Y graphs follow a convention like that of X11 screen coords? – Bruce Ediger May 16 '12 at 20:28
1

@BruceEdiger: I'm going to guess that it just comes down to different conventions. – FrustratedWithFormsDesigner May 16 '12 at 20:33
4

@BruceEdiger That's something quite different. The [Cartesian coordinate system](http://en.wikipedia.org/wiki/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: http://datamuseum.dk/w/images/5/5b/RC702_Tech_Man.pdf – May 17 '12 at 07: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 08:47
1

This answer and its comments reach back to hardware, printouts, terminals, and memory, all of which I feel had a lot to do with it. I'm marking this as the answer for the great comments as well as the answer. – maxpolk May 17 '12 at 21:56

score 1 · Answer 3 · answered May 17 '12 at 16:41

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.

score 0 · Answer 4 · answered Dec 07 '22 at 18:03

0

Computer science trees grow downward to ensure computer science gravity is consistent with computer science stacks.

If you don't like it, simply set gravity=-gravity.

answered Dec 07 '22 at 18:03

Alex Shroyer

125
4

This answer could be improved by explaining why computer science stacks also grow downwards – Adam B Dec 17 '22 at 19:56

Why do trees grow downward?

4 Answers4