Trees

The formula

E = V − 1

The signature of a tree. A connected graph on V nodes with no cycles has exactly V − 1 edges — count nodes and edges on any diagram claiming to be a tree, and if the arithmetic fails, somewhere there's a loop or a disconnected island.

T(n) = n^(n−2)

Cayley's formula: the number of distinct labeled trees on n nodes. Four labeled nodes give 4² = 16 trees; five give 125; ten give 10⁸. It is also the count of spanning trees of the complete graph on n nodes.

n_max = 2^(h+1) − 1        h_min = ceil( log₂(n+1) ) − 1

Binary tree capacity and depth. A binary tree of height h holds at most 2^(h+1) − 1 nodes, so a balanced tree with a million entries is only about 20 levels deep — 2²⁰ − 1 = 1,048,575.

C_n = (2n choose n) / (n + 1)

The Catalan number: how many distinct binary tree shapes exist on n nodes. C₃ = 5, C₄ = 14, C₁₀ = 16,796. This is the count of ways a parser can bracket an expression, which is why ambiguous grammars are a real problem and not a pedantic one.

AND gate:  P = P₁ · P₂        OR gate (rare events):  P ≈ P₁ + P₂

Fault tree gate math. An undesired event that requires two independent failures multiplies their probabilities; one that follows from either failure adds them (the exact OR is P₁ + P₂ − P₁·P₂, and the sum is a fine approximation only while both are small).

count of spanning trees = any cofactor of the graph Laplacian L = D − A

Kirchhoff's matrix-tree theorem. Build the degree-minus-adjacency matrix, strike any row and matching column, take the determinant: that number is how many distinct trees span the network.

Where you meet it

The safety review board. The poster-sized diagram on the wall with an undesired event at the top — inadvertent ignition, loss of range safety command — and AND/OR gates fanning down to component failures is a fault tree, the same structure the Air Force commissioned for Minuteman launch control in 1962. The board argues about the gate logic and the leaf probabilities; the tree does the bookkeeping.
The test data directory. Every file system is a rooted tree, and a path like /test/run_047/ch3.tdms works only because trees guarantee a unique route from root to leaf. The same structure holds your XML test procedures and every JSON config your DAQ software parses.
The network rack behind the test stand. Ethernet switches run a spanning tree protocol for a reason: a switched network with a physical loop and no protocol will forward broadcast frames around it forever. The protocol prunes the redundant links so live traffic flows on a tree, and re-forms a different tree when a link dies.
Any sorted lookup that finishes fast. The database indexing your telemetry archive walks a B-tree; a balanced binary search over a million-record table costs about 20 comparisons. When a query that should be instant takes seconds, the first question is whether the index — the tree — exists.

How it works

The load-bearing property is the unique path. A tree is simultaneously minimally connected — remove any edge and it splits in two — and maximally acyclic — add any edge between existing nodes and you create exactly one cycle. Everything else follows from that. It is why a tree gives an unambiguous chain of responsibility (one route from any leaf to the root), why cutting one branch cleanly removes one subtree and nothing else, and why a tree offers zero redundancy: a single failed edge disconnects it. When you want both hierarchy and fault tolerance, you carry redundant edges and let a protocol choose which tree is live at any moment. The redundancy is in the graph; the operation is on a tree.

A free tree has no direction. Parent, child, root, and depth exist only after you pick a root, and the same free tree rooted at two different nodes yields two different hierarchies. Fault trees root at the undesired event; file systems root at /; a parse tree roots at the whole expression. If two documents describe the same system with different-looking trees, check whether they just chose different roots before assuming a disagreement.

For binary trees the whole game is balance. A balanced tree with n nodes is log₂ n deep; a degenerate one is n deep — a linked list wearing a tree's name. The classic way to build the degenerate case is inserting already-sorted data into a naive binary search tree, which turns the promised 20-comparison lookup on a million records into an average of 500,000. This is exactly the mistake people make: loading a sorted export into an unbalanced structure and concluding the tool is slow. Self-balancing trees (AVL, red-black) and the B-trees inside every database exist because sorted input is the common case, not the pathological one.

Fault trees have their own gotcha, and it's the expensive one. The AND-gate multiplication P = P₁·P₂ is only valid when the two failures are independent. Two isolation valves at 10⁻³ each give 10⁻⁶ for the pair — unless they share a power bus, a hydraulic supply, a maintenance procedure, or a lot from the same bad production run, in which case one common cause fails both and the true number sits orders of magnitude above the tree's answer. Chasing common-cause failures out of the gate logic is most of the actual work of fault tree analysis; the multiplication is the easy part.

Last, counting. Tree shapes explode combinatorially: distinct unlabeled trees grow roughly like 2.956ⁿ ^[1], and labeled trees like n^(n−2). Any plan that begins "enumerate every possible topology" dies in the low tens of nodes. That is what Cayley's formula, the Catalan numbers, and the matrix-tree theorem are for — they count without enumerating, which is the difference between an answer and a job that outlives the program.

History

Trees entered engineering before they had a name. In 1847 Gustav Kirchhoff, working out how to solve current equations for electrical networks, used what we now call spanning trees to pick an independent set of loop equations, and proved the matrix-tree theorem — the number of spanning trees as a determinant — along the way ^[1]^[4]. Ten years later Arthur Cayley coined the word: his 1857 Philosophical Magazine paper "On the theory of the analytical forms called trees" named the branching structures he found while iterating differential operators ^[1]^[2]. Cayley kept pulling the thread. In 1874 he applied trees to chemistry, drawing "kenograms" — carbon skeletons with the hydrogens erased — to enumerate the isomers of the alkanes, and in 1875 published counts up to thirteen carbons. The last two were wrong, which is its own lesson about hand enumeration of trees ^[5]^[6]. The formula bearing his name, n^(n−2), was actually proved first by Carl Borchardt in 1860 via a determinant; Cayley's 1889 note extended it, cited Borchardt, and got the naming rights anyway ^[3].

The fault tree is younger and closer to home. In 1962, H. A. Watson at Bell Telephone Laboratories, under an Air Force contract, developed the technique to evaluate the launch control system of the Minuteman I ICBM — the question being whether the missile could launch when nobody told it to ^[7]^[8]. Only three top events were needed to cover the safety of that system, a demonstration of how much a well-rooted tree compresses ^[9]. The method spread through aerospace in the 1960s and was codified for the nuclear industry when Vesely, Goldberg, Roberts, and Haasl published the NRC's Fault Tree Handbook, NUREG-0492, in January 1981 — still the reference an FTA argument gets settled against ^[9].

Related tools

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →