Treewright — tree drawing tool and guide

A field guide to trees

Every tree here has the same bones — one root, branches, leaves — but each kind exists to answer a different question. This guide explains what each one is for, the rules that keep it valid, and how to read the drawings above.

Tree vocabulary

In mathematics a tree is a connected graph with no cycles. The trees in this tool are rooted: one node is picked as the starting point, and every other node hangs beneath it. A few facts follow from that definition and hold for every tree on this page: a tree with n nodes always has exactly n − 1 edges, and there is exactly one path between any two nodes.

Root: The single node with no parent. In a dependency tree it is usually the main verb; in a file system it is the top folder.
Parent, child, sibling: A node directly above another is its parent; the node below is its child. Children of the same parent are siblings.
Leaf and internal node: A leaf has no children. Every other node is internal. In a syntax tree the leaves are the words.
Depth, level and height: The depth of a node is the number of edges from the root down to it. The height of a tree is the depth of its deepest leaf. This tool counts height in edges, so a single node has height 0.
Subtree: Any node together with everything below it. Most tree algorithms work by solving a problem for each subtree and combining the answers.
Degree and branching factor: The number of children a node has. A binary tree allows at most two, and it matters which one is the left child and which is the right.
Traversal: A fixed order for visiting every node. Pre-order visits a node before its children, post-order after them, in-order (binary trees only) between the left and right child, and level-order goes row by row from the top.

Dependency trees

A dependency tree shows how the words of a sentence depend on one another. There are no phrase nodes at all: every node is a word, and every arrow runs from a head to one of its dependents, labelled with the grammatical relation between them. In the lazy dog, the noun dog is the head, and the and lazy depend on it.

The approach is associated with the French linguist Lucien Tesnière, whose book Éléments de syntaxe structurale was published in 1959, though the idea that words govern other words is much older and appears in the Sanskrit and Arabic grammatical traditions. Today most dependency work follows Universal Dependencies (UD), a shared annotation scheme with treebanks for well over 100 languages.

What makes a dependency tree valid

Exactly one word is the root. In UD it attaches to an invisible node 0 with the relation root.
Every other word has exactly one head.
Following heads upward from any word always reaches the root, so there are no cycles.

Treewright checks all three rules and tells you which line breaks them. A single word may have many dependents, but never two heads.

Projectivity

A tree is projective when its arcs can be drawn above the sentence without crossing. English is mostly projective, but crossing arcs appear with discontinuous structures such as A hearing is scheduled on the issue today, where on the issue belongs to hearing but is separated from it. Languages with freer word order, such as Czech, German or Latin, produce them more often. Crossing arcs are drawn dashed in the warning colour so you can spot them.

Common UD relations

Relation	Meaning	Example (head → dependent)
nsubj	nominal subject	jumps → fox
obj / iobj	direct / indirect object	gave → book / gave → brother
obl	oblique nominal (often with a preposition)	jumps → dog
amod	adjective modifying a noun	dog → lazy
det	determiner	dog → the
case	preposition, postposition or case marker	dog → over
advmod	adverb modifier	ran → quickly
aux / cop	auxiliary / copula	eating → is / happy → is
mark	subordinating marker	left → because
cc / conj	coordinator / conjunct	tea → coffee, coffee → and
compound	compound word part	station → bus
punct	punctuation	jumps → .

One UD design choice surprises many people: content words are heads, function words are dependents. The preposition over hangs from dog, not the other way round, and the auxiliary is hangs from the main verb. This makes languages comparable: an English preposition, an Urdu or Hindi postposition such as ko, and a Finnish case ending all end up in the same position in the tree.

Dependency or constituency?

The two describe the same sentence from different angles. Constituency trees show which words group into phrases; dependency trees show which word governs which. Dependency trees are smaller (one node per word), cope well with free word order, and feed directly into tasks like information extraction — for instance, finding every object of the verb acquire in a news corpus. Parsers such as spaCy, Stanza and UDPipe produce them.

Reading the input

Each line is id word head relation POS. The simplest valid tree is one word with head 0. Full CoNLL-U, the tab-separated format used by UD treebanks, also works; its ten columns are ID, FORM, LEMMA, UPOS, XPOS, FEATS, HEAD, DEPREL, DEPS and MISC. Multiword token lines such as 1-2 and empty nodes such as 8.1 are skipped. Switch the view to Hierarchy to see the same analysis as a top-down tree.

Try it: load the “Crossing arcs” example.

Constituency (phrase structure) trees

A constituency tree shows how a sentence breaks into nested phrases. The top node is usually S (sentence); it splits into a noun phrase (NP) and a verb phrase (VP), which split again, until you reach single words at the leaves. The labels just above the words are parts of speech, sometimes called preterminals.

This style comes from phrase structure grammar, formalised by Noam Chomsky in the 1950s, and it is the tree most syntax courses start with.

How linguists decide what counts as a phrase

A group of words is a constituent if it behaves as a unit. The standard tests:

Substitution: the old man can be replaced by he, so it is a phrase.
Movement: On the mat, the cat sat — the moved string is a phrase.
Coordination: only like constituents join with and: the cat and the dog.
Question answers: Where did the cat sit? On the mat.
Ellipsis: Sara will sit on the mat and Ali will too — the missing words form a VP.

No single test is perfect, so analysts look for agreement between several.

Structural ambiguity

One string can have two trees. In I saw the man with the telescope, the prepositional phrase can attach to the verb phrase (I used the telescope) or inside the noun phrase (the man had it). Treewright includes both analyses as examples so you can compare them. Garden-path sentences such as The horse raced past the barn fell are hard because readers build the wrong tree first.

X-bar theory

X-bar theory proposes that every phrase has the same shape regardless of category: a head X combines with a complement to form X′, which can take adjuncts, and a specifier joins to complete XP. The result is strictly binary branching. Treewright reports whether your tree is binary-branching throughout, which is a quick check when you practise X-bar trees. Write the bar level as N' or Nbar.

Reading the input

Write labelled brackets: an opening bracket, the label, then the contents, then a closing bracket — [NP [Det the] [N cat]]. Round brackets, as used in the Penn Treebank, also work: (NP (DT the) (NN cat)). Use underscores for multi-word leaves, such as New_York. If a bracket is missing, the message gives the line and column of the problem.

Uses beyond teaching include treebanks for training parsers, the CKY parsing algorithm for context-free grammars, grammar checking, and psycholinguistic research on sentence processing.

Syntax notation: everything you can mark

All the bracket-based syntax trees in Treewright (constituency, X-bar, movement, minimalist, cartographic, word structure, semantic, TAG, LFG and Relational Grammar) share one notation. Start with ordinary labelled brackets and add marks only where you need them.

You want	Write	Drawn as
An index	which_road_i, t_i, PRO_j, _{1,2}	a small lowered letter or number
A superscript	X^{max}	a small raised word
A feature bundle	Ø[+Q], T[uφ, EPP], NP[nom]	smaller purple text beside the label
A boxed node (trace, PRO)	{t_i}, {PRO}	the word in a box
A lower copy	<the_student>	grey and struck through
A triangle (unanalysed phrase)	[DP^ the red cover]	a triangle over the words
A highlighted node	NP!	a tinted pill
An arc label	[NP@SUBJ …], [NP@2,1 …]	a label on the line above the node
A note under or over a label	[VP::"⟨e,t⟩ : λx.sleep(x)" …]	small text with the label
An id for arrows	t_i#tr, what#wh	nothing; used by move: and link:
A movement arrow	move: tr -> wh "wh-movement"	a dashed curved arrow under the tree
A plain link	link: a -- b "binds" solid	a curve without arrowheads
A title and subtitle	title: …, subtitle: …	a heading above the drawing
A side panel	panel: Key - CP -> Complementizer Phrase	a boxed list on the right, arrows lined up
A note under the tree	note: The core relationships - …	a bulleted list below
Several trees side by side	tree: D-structure	a caption under each tree
A literal bracket or #	\[, \], \#	the character itself

Arrow lines take extra words in any order: dashed or solid, above to curve over the tree, and a colour (red, green, grey, black). The arrow points at the node after ->; use <-, <-> or -- for other directions. Tick “Hand-drawn look” to get the sketched style of a classroom handout.

Try it: the movement tree for “Which road is easy to cross?” uses nearly every mark.

X-bar trees

X-bar theory (Chomsky 1970, Jackendoff 1977) claims that every phrase, whatever its category, is built on the same three-level template. The head X combines with its complement to make X′; an adjunct can attach to X′ to make another X′; a specifier completes the maximal projection XP.

Complement: sister to the head, selected by it. of physics in student of physics.
Adjunct: sister to X′, optional and repeatable. with long hair.
Specifier: sister to the highest X′. Subjects sit in Spec-TP, determiners once sat in Spec-NP.

The test that separates complements from adjuncts: complements must come closer to the head, and one-replacement can target N′ but not N — the student of chemistry and the one with long hair, but not *the one of physics.

Head direction varies between languages while the template stays the same. English is head-initial (read a book); Urdu, Hindi, Japanese and Turkish are head-final (kitaab parhi).

What the checker looks for

With “Check X-bar rules” ticked, Treewright warns when a node has more than two children, or when an XP or X′ does not contain a projection of its own category. It is a reminder, not a proof: triangles and specifier labels are skipped.

Try it: compare where the two PPs attach.

Movement trees (Government and Binding)

In Government and Binding theory, a sentence has an underlying D-structure where every phrase sits where it gets its thematic role, and a surface S-structure produced by Move α. A moved phrase leaves a trace (t) that shares its index, and the pair forms a chain. Textbooks in the style of Andrew Carnie box traces and null elements and draw the movement as an arrow.

The null elements

t (trace): The empty position a phrase moved out of. It keeps the thematic role, and the chain carries Case.
PRO: The silent subject of a non-finite clause, as in Ali wants [PRO to leave]. Its reference is fixed by a controller.
pro: A silent pronoun in finite clauses of pro-drop languages such as Urdu, Italian and Spanish.
Ø: A silent head, such as an interrogative complementiser C[+Q] or present tense T.

Kinds of movement

Wh-movement to Spec-CP: What will you buy t?
Head movement, such as T-to-C in English questions, or V-to-T in French.
A-movement (NP movement) to Spec-TP for Case: passives and raising verbs such as seem.

Movement goes up: the landing site must c-command its trace. A node c-commands everything its sister contains. The “Chains and links” table below the drawing checks this for every arrow. The same relation drives Binding Theory: a reflexive such as herself needs a c-commanding antecedent in its own clause (Principle A).

Try it: see raising and control side by side.

Minimalist trees

The Minimalist Program (Chomsky 1995 onwards) builds structure with one operation, Merge, which takes two objects and makes a set. External Merge adds new material; internal Merge re-merges something already in the tree, which is movement. Because nothing is really removed, the lower position is a copy, not a trace, and it is simply not pronounced. Treewright draws lower copies struck through.

Little v introduces the agent in its specifier; the verb raises from V to v, giving the vP shell.
Features drive movement and agreement. Uninterpretable features such as [uφ] on T must be valued by Agree with a matching interpretable feature [iφ].
Phases (CP and vP) are sent to interpretation in chunks, so long-distance movement stops at each phase edge.
Bare phrase structure drops bar levels altogether: a phrase is labelled by its head.

Try it: follow what through the vP edge.

Cartographic trees

The cartographic programme maps the clause in fine detail, on the idea that each piece of meaning has its own head. Luigi Rizzi (1997) split CP into ForceP, TopP, FocP and FinP; Jean-Yves Pollock (1989) split IP into agreement, tense and negation phrases; Guglielmo Cinque (1999) proposed a universal order of adverb positions, from speech-act adverbs such as frankly down to aspect adverbs such as usually.

The evidence is order: frankly, fortunately, probably occurs in that order across many languages, and French finite verbs appear before pas because they have raised past NegP. The trees are tall, so the examples load with compact spacing.

Try it: see topic and focus in the left periphery.

Word structure trees

Morphologists use trees to show the order in which a word is built. Each affix attaches to a base of a particular category and may change it: -able turns a verb into an adjective, un- can attach to verbs (unlock) or adjectives (unkind). When two orders are possible, the word is ambiguous, just as a sentence can be.

Compounds are ambiguous in the same way: a school bus driver drives a school bus, or is a bus driver at a school. Inflection such as -s normally attaches last, outside derivation.

Try it: the two readings of unlockable.

Semantic (LF) trees

Formal semantics in the tradition of Heim and Kratzer computes a sentence’s meaning from its tree. Each node has a type — e for individuals, t for truth values, ⟨e,t⟩ for one-place predicates — and a meaning written in lambda notation. The main rule is function application: a node of type ⟨a,b⟩ combines with its sister of type a to give b. Predicate modification joins two ⟨e,t⟩ predicates with “and”.

Quantified phrases such as every student have type ⟨⟨e,t⟩,t⟩, so in object position they cannot combine directly. Quantifier raising moves them at Logical Form, leaving a trace and a numbered λ-binder; the height of each quantifier then fixes the scope.

Try it: check that every node’s type adds up.

Tree-adjoining grammar

Tree-adjoining grammar (Joshi, from 1975) starts from small elementary trees instead of rules. Initial trees (α) hold a word and slots for its arguments; auxiliary trees (β) hold optional material and a foot node marked * with the same label as their root.

Substitution plugs an initial tree into a slot marked ↓.
Adjunction splits a tree at a node and inserts an auxiliary tree there; the lower part hangs from the foot.

The derived tree is the result; the derivation tree records which tree went where, using Gorn addresses (2.2 is the second child of the second child). TAG is slightly more powerful than context-free grammar, enough for crossed dependencies such as those in Swiss German.

Try it: the derived and derivation trees together.

LFG: c-structure and f-structure

Lexical-Functional Grammar (Kaplan and Bresnan 1982) describes a sentence with two parallel structures. The c-structure is a phrase structure tree of the words in their actual order. The f-structure is an attribute-value matrix of grammatical functions — SUBJ, OBJ, XCOMP — and features such as tense and case.

Annotations on the tree connect the two. ↑ means “my mother’s f-structure” and ↓ means “my own”, so (↑SUBJ)=↓ on an NP says “I am my clause’s subject”, and ↑=↓ says “I am the head; share my features”. Because functions, not positions, carry the grammar, LFG handles free word order and case-marking languages such as Urdu and Warlpiri naturally.

A tag such as [1] written twice means one shared value, used for control: in Sara wants to leave, the subject of leave is the same f-structure as the subject of wants.

Try it: Urdu ergative case and object agreement.

HPSG feature structures

Head-driven Phrase Structure Grammar (Pollard and Sag 1994) describes every word and phrase as a sign: a typed attribute-value matrix holding its sound (PHON), syntax and meaning (SYNSEM). The type, written in italics at the top of a matrix, comes from a type hierarchy, which is itself a tree.

Grammar is mostly in the lexicon. A verb lists what it needs in SUBJ and COMPS; a few general schemata combine a head with its complements or subject. The Head Feature Principle makes a phrase share its HEAD value with its head daughter, drawn as the same boxed tag [1] in both places. Structure sharing, not movement, does the work.

Try it: a lexical entry with structure sharing.

CCG derivations

Combinatory Categorial Grammar (Steedman) puts almost all of the grammar in word categories. NP and S are basic; X/Y is a function that wants a Y on its right to become an X, and X\Y wants a Y on its left. A transitive verb is (S\NP)/NP: object to the right, then subject to the left.

Derivations are drawn upside down: words on top, a line under each combination, the rule on the right. Treewright searches all combinations with the CKY algorithm and draws the first derivation that reaches your goal category.

> and < (application): Apply a function to its argument.
>B and <B (composition): Join two functions before their argument arrives, so Ali read can be a unit of type S/NP.
>T and <T (type-raising): Turn an argument into a function over the verbs that take it, so subjects can compose with verbs.
Φ (coordination): Join two constituents of the same category with conj. With composition and raising, even non-traditional constituents coordinate: Ali cooked and Sara ate the rice.

Try it: coordination that needs type-raising.

Reed–Kellogg sentence diagrams

Alonzo Reed and Brainerd Kellogg published this system in 1877, and it was the standard way of teaching grammar in American schools for a century. It is not a tree of phrases but a picture of the parts of a sentence.

The baseline holds the subject, verb and object or complement.
A line crossing the baseline separates subject and verb.
A short upright line stands before a direct object; a line slanting back towards the subject stands before a subject complement (is clever).
Modifiers sit on slanted lines under the word they modify. A prepositional phrase has its preposition on the slant and its object on a horizontal line.
Compound parts fork into parallel lines joined by a dotted line with the conjunction.

Reed–Kellogg diagrams are good for spotting what modifies what, but they ignore word order and cannot show the difference between complements and adjuncts, which is why linguists moved to trees.

Try it: a compound subject with an indirect object.

Relational Grammar

Relational Grammar (Perlmutter and Postal, 1970s) treats grammatical relations as primitive. A clause is a set of arcs from the clause node to its parts, each arc labelled with a relation at every level, or stratum: P predicate, 1 subject, 2 direct object, 3 indirect object.

Constructions are changes between strata. In the passive, the 2 advances to 1 and the old 1 becomes a chômeur (“unemployed”), written Cho. Dative shift is 3 advancing to 2. The Unaccusative Hypothesis, which began in Relational Grammar, says the subject of verbs such as melt starts as a 2.

Each arc label in Treewright lists the strata from first to last, so 2, 1 reads “object in stratum 1, subject in stratum 2”.

Try it: the passive as a stratal diagram.

General trees (hierarchies)

A general tree lets each node have any number of children. It is the shape of an organisation chart, a folder structure, a table of contents, a biological taxonomy, the HTML document object model, or a book broken into parts, chapters and sections.

A note on family trees: a full genealogy is not strictly a tree, because every person has two parents and cousins can marry, so the structure can loop back. A descendant chart (one ancestor and everyone below) is a true tree, and that is what the family example draws.

Useful properties

With n nodes there are always n − 1 parent–child links.
Pre-order traversal gives the order you would read an outline in; post-order is the order you would need to delete folders (contents first).
Any general tree can be stored as a binary tree using the left-child, right-sibling method, which is how some file systems and compilers store them.

Reading the input

Write one item per line and indent children beneath their parent with spaces or tabs. The amount of indentation only needs to be deeper than the parent's. Bullet markers (-, *) and the box-drawing characters from command-line tree output are ignored, so you can paste a folder listing directly. Add a second line of text to a node after | . If you write several top-level items, they are drawn side by side as a forest.

Binary search trees

A binary search tree (BST) stores keys so they can be found quickly. It obeys one rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger. To find a key, start at the root and go left or right at each step; each comparison discards a whole subtree.

How insertion works

Start at the root. If the tree is empty, the new key becomes the root.
Compare the key with the current node: go left if it is smaller, right if it is larger.
When the chosen side is empty, attach the key there as a new leaf.

Duplicates are skipped here, which is the most common convention.

How deletion works

There are three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children takes the value of its in-order successor (the smallest key in its right subtree), and that successor is then removed from below. Use the “Then delete” box to watch each case.

Why order matters

The shape depends entirely on insertion order. Random orders tend to give a height around 2–3 × log₂n, but inserting already-sorted keys produces a chain with height n − 1, and searching becomes as slow as scanning a list. Type 1 2 3 4 5 6 7 to see it. Self-balancing trees such as AVL and red-black trees exist to prevent this.

An in-order traversal of any BST lists its keys in sorted order — a handy way to check a tree is valid. The number of differently shaped BSTs with n keys is the n-th Catalan number: 5 shapes for 3 keys, 42 for 5.

Operation	Average	Worst case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

AVL trees

The AVL tree, published by Georgy Adelson-Velsky and Evgenii Landis in 1962, was the first self-balancing binary search tree. It keeps the BST ordering rule and adds one more: at every node, the heights of the left and right subtrees differ by at most one. That difference is the balance factor (left height minus right height), and Treewright shows it under each key.

Rebalancing after an insert

Insert the key exactly as in a plain BST.
Walk back up toward the root, updating heights.
At the first node whose balance factor becomes +2 or −2, apply one of four fixes.

Case	Shape	Fix
Left-left	new key in left child's left subtree	single right rotation
Right-right	new key in right child's right subtree	single left rotation
Left-right	new key in left child's right subtree	left rotation on the child, then right rotation
Right-left	new key in right child's left subtree	right rotation on the child, then left rotation

A rotation is a local rearrangement of three nodes that keeps the left-smaller, right-larger order intact while shifting height from one side to the other. The step log under the drawing records every rotation.

The height of an AVL tree is always below about 1.44 × log₂(n + 2), so search, insert and delete are guaranteed O(log n). AVL trees are more tightly balanced than red-black trees, which makes lookups slightly faster but can mean more rotations during updates. They suit read-heavy workloads such as in-memory indexes. Compare the stats panel: it shows how tall a plain BST would be for the same input.

Red-black trees

A red-black tree is another self-balancing BST. Instead of storing heights, each node carries one bit of colour, and five rules keep the tree roughly balanced:

Every node is red or black.
The root is black.
Every empty (NIL) leaf position counts as black.
A red node never has a red child.
Every path from a node down to a NIL leaf passes through the same number of black nodes — the black height.

Together these guarantee that the longest root-to-leaf path is at most twice the shortest, so the height is at most 2 × log₂(n + 1). Treewright verifies all five rules after drawing.

Fixing the tree after an insert

A new node is inserted as red, which can only break rule 4 (or rule 2 if it is the root). The repair looks at the new node's uncle — its parent's sibling:

Uncle is red: recolour the parent and uncle black and the grandparent red, then continue checking from the grandparent.
Uncle is black, and the node is on the inside: rotate it to the outside first.
Uncle is black, and the node is on the outside: rotate at the grandparent and swap the colours of the parent and grandparent. The tree is then valid.

Red-black trees need at most two rotations per insertion, which makes them popular for general-purpose libraries: Java's TreeMap, most implementations of C++ std::map, and many parts of the Linux kernel use them. They are closely related to 2-3-4 trees — a black node together with its red children corresponds to one 2-3-4 node.

Heaps

A binary heap is a complete binary tree — every level is full except possibly the last, which fills from the left — with one ordering rule. In a min-heap every parent is smaller than or equal to its children, so the smallest key is always at the root. A max-heap is the reverse. Unlike a BST, there is no order between siblings, so a heap is not useful for searching; it is built for repeatedly taking out the smallest (or largest) item.

Stored as an array

Because a complete tree has no gaps, it fits neatly in an array read level by level. For the node at index i (starting from 0), the children are at 2i + 1 and 2i + 2, and the parent is at ⌊(i − 1) / 2⌋. Turn on “Show array index” to see the positions. No pointers are needed, which makes heaps compact and fast in practice.

Operations

Insert: place the key in the next free position, then sift up — swap it with its parent while it breaks the heap rule. O(log n).
Extract the root: move the last key to the root, then sift down — swap it with its smaller child (min-heap) until the rule holds. O(log n).
Peek: read the root. O(1).
Build from a list: Floyd's method sifts down every internal node from the bottom up and runs in O(n), faster than n separate inserts. Compare the swap counts for the two build methods.

Heaps power priority queues, which appear in Dijkstra's shortest-path algorithm, operating-system and event schedulers, heapsort, merging sorted files, and “top k” queries.

Tries (prefix trees)

A trie stores a set of words one character per level. The path from the root to a node spells a prefix, and nodes where a complete word ends are marked — filled in the drawing. Words that share a beginning share a path, so tea, ten and to all start from the same t. The structure was described by René de la Briandais in 1959, and Edward Fredkin named it in 1960 after the middle of retrieval.

Why use one

Looking up a word of length m takes O(m) steps, however many words are stored.
Every word starting with a prefix sits in one subtree, which makes autocomplete and predictive text natural.
Spell checkers, word games, dictionary compression and IP routing (longest-prefix matching) all use tries or their variants.

Radix trees

A plain trie wastes nodes on long chains with no branching. A radix tree (or compressed trie, closely related to a PATRICIA tree) merges each such chain into a single node labelled with several characters. Tick “Compress chains” to see the same words stored with fewer nodes. The trade-off throughout is memory: tries can use a lot of it when the alphabet is large, which is why real implementations use arrays, hash maps or bit tricks for the child links.

Tries work for any script. Unicode letters, including Urdu or Devanagari, are handled one character at a time.

Expression trees

An expression tree represents a calculation: internal nodes are operators or functions, and leaves are numbers or variables. The rules of precedence and associativity that you normally have to remember become visible structure. In 3 + 4 × 2, the multiplication sits lower in the tree, so it is worked out first.

Three ways to read the same tree

Pre-order gives prefix or Polish notation, introduced by Jan Łukasiewicz: + 3 × 4 2.
In-order gives ordinary infix notation, which needs brackets to be unambiguous.
Post-order gives postfix or reverse Polish notation: 3 4 2 × +. It needs no brackets and is how stack-based calculators and many virtual machines evaluate code.

Evaluating

To evaluate, work bottom-up in post-order: compute each subtree's value, then apply the parent's operator. The step list under the drawing follows exactly this order.

Rules used here

Powers bind tightest and group from the right, so 2^3^2 is 2⁹ = 512. A leading minus applies after powers, so -2^2 is −4. Multiplication, division and % come next, then addition and subtraction, all grouping left to right. Supported functions: sqrt, abs, sin, cos, tan, ln, log (base 10), exp, floor, ceil, round, min and max. The constants pi and e are built in.

Compilers build a close relative, the abstract syntax tree, for whole programs, and computer algebra systems manipulate expression trees to simplify and differentiate formulas.

Huffman coding trees

A Huffman tree builds the shortest possible prefix code for a piece of text, given how often each symbol appears. David Huffman devised it in 1952 as a student. Frequent symbols get short codes and rare symbols get long ones.

How the tree is built

Count how often each symbol appears. Each symbol starts as a leaf.
Take the two nodes with the lowest counts and join them under a new parent whose count is their sum.
Repeat until a single node remains. That node is the root.
Label every left branch 0 and every right branch 1. A symbol's code is the sequence of labels from the root to its leaf.

Why it works

Symbols only ever sit on leaves, so no code can be the beginning of another. That prefix-free property means a stream of bits can be decoded without separators. Huffman's greedy method is provably optimal among codes that give each symbol a whole number of bits. When counts tie, different trees are possible, but they all give the same total length. The stats panel compares the result with plain 8-bit characters and with the text's entropy, the theoretical lower limit; the Huffman average is always within one bit of it.

Huffman coding is part of DEFLATE (used by ZIP, gzip and PNG), JPEG and MP3. Its limit is that each symbol costs at least one bit; arithmetic coding and asymmetric numeral systems get closer to the entropy for very skewed data.

Comparing the data-structure trees

Tree	Search	Insert	Delete	Best for
BST	O(log n) avg, O(n) worst	same	same	learning, random input
AVL	O(log n)	O(log n)	O(log n)	lookup-heavy work
Red-black	O(log n)	O(log n)	O(log n)	mixed updates, libraries
Binary heap	O(n)	O(log n)	O(log n) root	priority queues
Trie	O(m)	O(m)	O(m)	prefixes, autocomplete

n is the number of stored items; m is the length of the word being looked up.

Other trees worth knowing

B-trees and B+ trees: Search trees whose nodes hold many keys, so the tree stays very shallow. Designed for disks and SSDs, they underpin most database indexes and file systems.
Segment trees and Fenwick trees: Answer range questions — “what is the sum of items 20 to 80?” — and update single items, both in O(log n).
k-d trees, quadtrees, octrees and R-trees: Split space rather than keys. Used in maps, games, collision detection and nearest-neighbour search.
Suffix trees: Store every suffix of a text, allowing substring search in time proportional to the pattern. Common in bioinformatics.
Splay trees and treaps: Alternative self-balancing BSTs: splay trees move recently used keys to the root; treaps combine BST order with random heap priorities.
Decision trees: Each internal node asks a question about the data and each leaf gives a prediction. A core model in machine learning and the basis of random forests.
Game trees: Every possible sequence of moves from a position. The minimax algorithm with alpha-beta pruning searches them in chess and other games.
Spanning trees: A subset of a network's links that connects every node without loops. Minimum spanning trees (Kruskal's and Prim's algorithms) design cheap cable and road networks.
Abstract syntax trees: The expression-tree idea extended to whole programs; the central data structure inside compilers, linters and code formatters.
Morphological trees: Show the internal structure of words. unlockable has two trees: [un [lock able]] “cannot be locked” and [[un lock] able] “can be unlocked”. You can draw these with the constituency tool.
Phylogenetic trees: Show how species or languages descend from common ancestors; historical linguists use them for language families such as Indo-European. Draw them with the general hierarchy tool.