Tree (data structure)
This article needs additional citations for verification. (August 2010) (Learn how and when to remove this template message) 
In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Both these perspectives are useful: while a tree can be analyzed mathematically as a whole, when actually represented as a data structure it is usually represented and worked with separately by node (rather than as a set of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not contain a reference to its parent (if any).
Contents
Preliminary definition[edit]
A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.
Mathematical definition[edit]
Unordered tree[edit]
Mathematically, an unordered tree^{[1]} (or "algebraic tree"^{[2]}) can be defined as an algebraic structure (X, parent) where X is the nonempty carrier set of nodes and parent is a function on X which assigns each node x its "parent" node, parent(x). The structure is subject to the condition that every nonempty subalgebra must have the same fixed point. That is, there must be a unique "root" node r, such that parent(r) = r and for every node x, some iterative application parent(parent(…parent(x)…)) equals r.
There are several equivalent definitions. As the closest alternative, one can define unordered trees as partial algebras (X, parent) which are obtained from the total algebras described above by letting parent(r) be undefined. That is, the root r is the only node on which the parent function is not defined and for every node x, the root is reachable from x in the directed graph (X, parent). This definition is in fact coincident with that of an antiarborescence.
Another equivalent definition is that of a settheoretic tree that is singlyrooted and whose height is at most ω. That is, the algebraic structures (X, parent) are equivalent to partial orders (X, ≤) that have a top element r and whose every principal upset (aka principal filter) is a finite chain. To be precise, we should speak about an inverse settheoretic tree since the settheoretic definition usually employs opposite ordering. The correspondence between (X, parent) and (X, ≤) is established via reflexive transitive closure / reduction, with the reduction resulting in the "partial" version without the root cycle.
The definition of trees in descriptive set theory (DST) utilizes the representation of partial orders (X, ≥) as prefix orders between finite sequences. In turns out that up to isomorphism, there is a onetoone correspondence between the (inverse of) DST trees and the tree structures defined so far.
We can refer to the four equivalent characterizations as to tree as an algebra, tree as a partial algebra, tree as a partial order, and tree as a prefix order. There is also a fifth equivalent definition – that of a graphtheoretic rooted tree which is just a connected acyclic rooted graph.
The expression of trees as (partial) algebras (X, parent) follows directly the implementation of tree structures using parent pointers. Typically, the partial version is used in which the root node has no parent defined. However, in some implementations or models even the parent(r) = r circularity is established. Notable examples:
 The Linux VFS where "The root dentry has a d_parent that points to itself" ^{[3]}.
 The concept of an instantiation tree ^{[4]} ^{[5]} ^{[6]} from objectoriented programming. In this case, the root node is the top metaclass – the only class that is a direct instance of itself.
Note that the above definition admits infinite trees. This allows for the description of infinite structures supported by some implementations via lazy evaluation. A notable example is the infinite regress of eigenclasses from the Ruby object model.^{[7]}
In this model, the tree established via superclass
links between nonterminal objects is infinite and has an infinite branch (a single infinite branch of "helix" objects – see the diagram).
Sibling sets[edit]
In every unordered tree (X, parent) there is a distinguished partition of the set X of nodes into sibling sets. Two nonroot nodes x, y belong to the same sibling set if parent(x) = parent(y). The root node r forms the singleton sibling set {r}. ^{[a]} A tree is said to be locally finite or finitely branching if each of its sibling sets is finite.
Each pair of distinct siblings is incomparable in ≤. This is why the word unordered is used in the definition. Such a terminology might become misleading when all sibling sets are singletons, i.e. when the set X of all nodes is totally ordered (and thus wellordered) by ≤. In such a case we might speak about a singlybranching tree instead.
Using set inclusion[edit]
As with every partially ordered set, tree structures (X, ≤) can be represented by containment order – by set systems in which ≤ is coincident with ⊆, the induced inclusion order. Consider a structure (U, ℱ) such that U is a nonempty set, and ℱ is a set of subsets of U such that the following are satisfied:
 ∅ ∉ ℱ. (That is, (U, ℱ) is a hypergraph.)
 U ∈ ℱ.
 For every X, Y from ℱ, X ∩ Y ∈ {∅, X, Y}. (That is, ℱ is a laminar family.^{[8]})
 For every X from ℱ, there are only finitely many Y from ℱ such that X ⊆ Y.
Then the structure (ℱ, ⊆) is an unordered tree whose root equals U. Conversely, if (U, ≤) is an unordered tree, and ℱ is the set {↓x  x ∈ U} of all principal ideals of (U, ≤) then the set system (U, ℱ) satisfies the above properties.
The setsystem view of tree structures provides the default semantic model – in the majority of most popular cases, tree data structures represent containment hierarchy. This also offers a justification for order direction with the root at the top: The root node is a greater container than any other node. Notable examples:
 Directory structure of a file system. A directory contains its subdirectories.
 DOM tree. The document parts corresponent to DOM nodes are in subpart relation according to the tree order.
 Single inheritance in objectoriented programming. An instance of a class is also an instance of a superclass.
 Hierarchical taxonomy such as the Dewey Decimal Classification with sections of increasing specificity.
 BSP trees, quadtrees, octrees, Rtrees and other tree data structures used for recursive space partitioning.
Ordered tree[edit]
The structures introduced in the previous subsection form just the core "hierarchical" part of tree data structures that appear in computing. In most cases, there is also an additional "horizontal" ordering between siblings. The correspondent expansion of the previously described tree structures (X, ≤) can be defined as follows.
An ordered tree is a structure (X, ≤_{V}, ≤_{S}) where X is a nonempty set of nodes and ≤_{V} and ≤_{S} are relations on X called vertical (or also hierarchical^{[1]}) order and sibling order, respectively. The structure is subject to the following conditions:
 (X, ≤_{V}) is a partial order that is an unordered tree as defined in the previous subsection.
 (X, ≤_{S}) is a partial order.
 The partial orders ≤_{V} and ≤_{S} are orthogonal: ((<_{V}) ∪ (>_{V})) ∩ ((<_{S}) ∪ (>_{S})) = ∅. That is, distinct nodes cannot be comparable both in ≤_{V} and ≤_{S}.
 For every sibling set S of (X, ≤_{V}), the restriction (S, ≤_{S}) is a singlybranching tree. That is, (S, ≤_{S}) is a linear order, and if S is infinite, then (S, ≤_{S}) must be isomorphic to (ℕ, ≤), the usual ordering of natural numbers.
Given this, there are three distinguished partial orders which are uniquely given by the following prescriptions:
(<_{H}) = (≤_{V}) ○ (<_{S}) ○ (≥_{V}) (the horizontal order), (<_{L⁻}) = (>_{V}) ∪ (<_{H}) (the "discordant" linear order), (<_{L⁺}) = (<_{V}) ∪ (<_{H}) (the "concordant" linear order).
This amounts to a "VSHL^{±}" system of five partial orders ≤_{V}, ≤_{S}, ≤_{H}, ≤_{L⁺}, ≤_{L⁻} on the same set X of nodes, in which, except for the pair { ≤_{S}, ≤_{H} }, any two relations uniquely determine the other three.
Notes about notational conventions:
 The relation composition symbol ○ used in this subsection is to be interpreted lefttoright (as ).
 Symbols < and ≤ express the strict and nonstrict versions of a partial order.
 Symbols > and ≥ express the converse relations.
 The ≺ symbol is used for the covering relation of ≤ which is the immediate version of a partial order.
This yields six versions ≺, <, ≤, ≻, >, ≥ for a single partial order relation. Except for ≺ and ≻, each version uniquely determines the others. Passing from ≺ to < requires that < be transitively reducible. This is always satisfied for all of <_{V}, <_{S} and <_{H} but might not hold for <_{L⁺} or <_{L⁻}.
The partial orders ≤_{V} and ≤_{H} are complementary: (<_{V}) ⊎ (>_{V}) ⊎ (<_{H}) ⊎ (>_{H}) = X × X ∖ id_{X}. As a consequence, the "concordant" linear order <_{L⁺} is a linear extension of <_{V}. Similarly, <_{L⁻} is a linear extension of >_{V}.
The covering relations ≺_{L⁻} and ≺_{L⁺} correspond to preorder traversal and postorder traversal, respectively. If x ≺_{L⁻} y then, according to whether y has a previous sibling or not, the x node is either the "rightmost" nonstrict descendant of the previous sibling of y or, in the latter case, x is the first child of y. Pairs (x,y) of the latter case form the relation (≺_{L⁻}) ∖ (<_{H}) which is a partial map that assigns each nonleaf node its first child node. Similarly, (≻_{L⁺}) ∖ (>_{H}) assigns each nonleaf node with finitely many children its last child node.
XPath Axes[edit]
XPath Axis  Relation 

ancestor

<_{V} 
ancestororself

≤_{V} 
child

≻_{V} 
descendant

>_{V} 
descendantorself

≥_{V} 
following

<_{H} 
followingsibling

<_{S} 
parent

≺_{V} 
preceding

>_{H} 
precedingsibling

>_{S} 
self

id_{X} 
The table on the right shows a correspondence of introduced relations to XPath axes. For a context node^{[9]} x, its axis named by the specifier in the left column is the set of nodes that equals the image of {x} under the correspondent relation. As of XPath 2.0, the nodes are "returned" in document order, which is the "discordant" linear order ≤_{L⁻}. A "concordance" would be achieved, if the vertical order ≤_{V} was defined oppositely, with the bottomup direction outwards the root like in set theory in accordance to natural trees.^{[b]}
Traversal maps[edit]
Below is the list of partial maps that are typically used for ordered tree traversal.^{[10]} Each map is a distinguished functional subrelation of ≤_{L⁻} or of its opposite.
 ≺_{V} … the parentnode partial map,
 ≻_{S} … the previoussibling partial map,
 ≺_{S} … the nextsibling partial map,
 (≺_{L⁻}) ∖ (<_{H}) … the firstchild partial map,
 (≻_{L⁺}) ∖ (>_{H}) … the lastchild partial map,
 ≻_{L⁻} … the previousnode partial map,
 ≺_{L⁻} … the nextnode partial map.
Generating structure[edit]
The traversal maps constitute a partial unary algebra^{[11]} (X, parent, previousSibling, …, nextNode) that forms a basis for representing trees as linked data structures. At least conceptually, there are parent links, sibling adjacency links, and first / last child links. This also applies to unordered trees in general, which can be observed on the dentry data structure in the Linux VFS.^{[12]}
Similarly to the "VSHL^{±}" system of partial orders, there are pairs of traversal maps that uniquely determine the whole ordered tree structure. Naturally, one such generating structure is (X, ≺_{V}, ≺_{S}) which can be transcribed as (X, parent, nextSibling) – the structure of parent and nextsibling links. Another important generating structure is (X, firstChild, nextSibling) known as leftchild rightsibling binary tree. This partial algebra establishes a onetoone correspondence between binary trees and ordered trees.
Definition using binary trees[edit]
The correspondence to binary trees provides a concise definition of ordered trees as partial algebras.
An ordered tree is a structure (X, lc, rs) where X is a nonempty set of nodes, and lc, rs are partial maps on X called leftchild and rightsibling, respectively. The structure is subject to the following conditions:
 The partial maps lc and rs are disjoint, i.e. (lc) ∩ (rs) = ∅ .
 The inverse of (lc) ∪ (rs) is a partial map p such that the partial algebra (X, p) is an unordered tree.
The partial order structure (X, ≤_{V}, ≤_{S}) is obtained as follows:
(≺_{S}) = (rs), (≻_{V}) = (lc) ○ (≤_{S}).
Terminology used in trees[edit]
Data type versus data structure[edit]
There is a distinction between a tree as an abstract data type and as a concrete data structure, analogous to the distinction between a list and a linked list. As a data type, a tree has a value and children, and the children are themselves trees; the value and children of the tree are interpreted as the value of the root node and the subtrees of the children of the root node. To allow finite trees, one must either allow the list of children to be empty (in which case trees can be required to be nonempty, an "empty tree" instead being represented by a forest of zero trees), or allow trees to be empty, in which case the list of children can be of fixed size (branching factor, especially 2 or "binary"), if desired.
As a data structure, a linked tree is a group of nodes, where each node has a value and a list of references to other nodes (its children). There is also the requirement that no two "downward" references point to the same node. Nodes in a tree could have next/previous references or references to their parent nodes.
Due to the use of references to trees in the linked tree data structure, trees are often discussed implicitly assuming that they are being represented by references to the root node, as this is often how they are actually implemented. For example, rather than an empty tree, one may have a null reference: a tree is always nonempty, but a reference to a tree may be null.
Recursive[edit]
Recursively, as a data type a tree is defined as a value (of some data type, possibly empty), together with a list of trees (possibly an empty list), the subtrees of its children; symbolically:
t: v [t[1], ..., t[k]]
(A tree t consists of a value v and a list of other trees.)
More elegantly, via mutual recursion, of which a tree is one of the most basic examples, a tree can be defined in terms of a forest (a list of trees), where a tree consists of a value and a forest (the subtrees of its children):
f: [t[1], ..., t[k]] t: v f
Note that this definition is in terms of values, and is appropriate in functional languages (it assumes referential transparency); different trees have no connections, as they are simply lists of values.
As a data structure, a tree is defined as a node (the root), which itself consists of a value (of some data type, possibly empty), together with a list of references to other nodes (list possibly empty, references possibly null); symbolically:
n: v [&n[1], ..., &n[k]]
(A node n consists of a value v and a list of references to other nodes.)
This data structure defines a directed graph,^{[c]} and for it to be a tree one must add a condition on its global structure (its topology), namely that at most one reference can point to any given node (a node has at most a single parent), and no node in the tree point to the root. In fact, every node (other than the root) must have exactly one parent, and the root must have no parents.
Indeed, given a list of nodes, and for each node a list of references to its children, one cannot tell if this structure is a tree or not without analyzing its global structure and that it is in fact topologically a tree, as defined below.
Type theory[edit]
As an ADT, the abstract tree type T with values of some type E is defined, using the abstract forest type F (list of trees), by the functions:
 value: T → E
 children: T → F
 nil: () → F
 node: E × F → T
with the axioms:
 value(node(e, f)) = e
 children(node(e, f)) = f
In terms of type theory, a tree is an inductive type defined by the constructors nil (empty forest) and node (tree with root node with given value and children).
Mathematical[edit]
Viewed as a whole, a tree data structure is an ordered tree, generally with values attached to each node. Concretely, it is (if required to be nonempty):
 A rooted tree with the "away from root" direction (a more narrow term is an "arborescence"), meaning:
 A directed graph,
 whose underlying undirected graph is a tree (any two vertices are connected by exactly one simple path),
 with a distinguished root (one vertex is designated as the root),
 which determines the direction on the edges (arrows point away from the root; given an edge, the node that the edge points from is called the parent and the node that the edge points to is called the child),
together with:
 an ordering on the child nodes of a given node, and
 a value (of some data type) at each node.
Often trees have a fixed (more properly, bounded) branching factor (outdegree), particularly always having two child nodes (possibly empty, hence at most two nonempty child nodes), hence a "binary tree".
Allowing empty trees makes some definitions simpler, some more complicated: a rooted tree must be nonempty, hence if empty trees are allowed the above definition instead becomes "an empty tree, or a rooted tree such that ...". On the other hand, empty trees simplify defining fixed branching factor: with empty trees allowed, a binary tree is a tree such that every node has exactly two children, each of which is a tree (possibly empty).The complete sets of operations on tree must include fork operation.
Terminology[edit]
A node is a structure which may contain a value or condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child's parent node (or ancestor node, or superior). A node has at most one parent.
An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.
The topmost node in a tree is called the root node. Depending on definition, a tree may be required to have a root node (in which case all trees are nonempty), or may be allowed to be empty, in which case it does not necessarily have a root node. Being the topmost node, the root node will not have a parent. It is the node at which algorithms on the tree begin, since as a data structure, one can only pass from parents to children. Note that some algorithms (such as postorder depthfirst search) begin at the root, but first visit leaf nodes (access the value of leaf nodes), only visit the root last (i.e., they first access the children of the root, but only access the value of the root last). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique.) In diagrams, the root node is conventionally drawn at the top. In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node.
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various selfbalancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.^{[d]}^{[13]} Nodes thus correspond to subtrees (each node corresponds to the subtree of itself and all its descendants) – the subtree corresponding to the root node is the entire tree, and each node is the root node of the subtree it determines; the subtree corresponding to any other node is called a proper subtree (by analogy to a proper subset).
Drawing trees[edit]
Trees are often drawn in the plane. Ordered trees can be represented essentially uniquely in the plane, and are hence called plane trees, as follows: if one fixes a conventional order (say, counterclockwise), and arranges the child nodes in that order (first incoming parent edge, then first child edge, etc.), this yields an embedding of the tree in the plane, unique up to ambient isotopy. Conversely, such an embedding determines an ordering of the child nodes.
If one places the root at the top (parents above children, as in a family tree) and places all nodes that are a given distance from the root (in terms of number of edges: the "level" of a tree) on a given horizontal line, one obtains a standard drawing of the tree. Given a binary tree, the first child is on the left (the "left node"), and the second child is on the right (the "right node").
Representations[edit]
There are many different ways to represent trees; common representations represent the nodes as dynamically allocated records with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).
Indeed, a binary tree can be implemented as a list of lists (a list where the values are lists): the head of a list (the value of the first term) is the left child (subtree), while the tail (the list of second and subsequent terms) is the right child (subtree). This can be modified to allow values as well, as in Lisp Sexpressions, where the head (value of first term) is the value of the node, the head of the tail (value of second term) is the left child, and the tail of the tail (list of third and subsequent terms) is the right child.
In general a node in a tree will not have pointers to its parents, but this information can be included (expanding the data structure to also include a pointer to the parent) or stored separately. Alternatively, upward links can be included in the child node data, as in a threaded binary tree.
Generalizations[edit]
Digraphs[edit]
If edges (to child nodes) are thought of as references, then a tree is a special case of a digraph, and the tree data structure can be generalized to represent directed graphs by removing the constraints that a node may have at most one parent, and that no cycles are allowed. Edges are still abstractly considered as pairs of nodes, however, the terms parent and child are usually replaced by different terminology (for example, source and target). Different implementation strategies exist: a digraph can be represented by the same local data structure as a tree (node with value and list of children), assuming that "list of children" is a list of references, or globally by such structures as adjacency lists.
In graph theory, a tree is a connected acyclic graph; unless stated otherwise, in graph theory trees and graphs are assumed undirected. There is no onetoone correspondence between such trees and trees as data structure. We can take an arbitrary undirected tree, arbitrarily pick one of its vertices as the root, make all its edges directed by making them point away from the root node – producing an arborescence – and assign an order to all the nodes. The result corresponds to a tree data structure. Picking a different root or different ordering produces a different one.
Given a node in a tree, its children define an ordered forest (the union of subtrees given by all the children, or equivalently taking the subtree given by the node itself and erasing the root). Just as subtrees are natural for recursion (as in a depthfirst search), forests are natural for corecursion (as in a breadthfirst search).
Via mutual recursion, a forest can be defined as a list of trees (represented by root nodes), where a node (of a tree) consists of a value and a forest (its children):
f: [n[1], ..., n[k]] n: v f
Traversal methods[edit]
Stepping through the items of a tree, by means of the connections between parents and children, is called walking the tree, and the action is a walk of the tree. Often, an operation might be performed when a pointer arrives at a particular node. A walk in which each parent node is traversed before its children is called a preorder walk; a walk in which the children are traversed before their respective parents are traversed is called a postorder walk; a walk in which a node's left subtree, then the node itself, and finally its right subtree are traversed is called an inorder traversal. (This last scenario, referring to exactly two subtrees, a left subtree and a right subtree, assumes specifically a binary tree.) A levelorder walk effectively performs a breadthfirst search over the entirety of a tree; nodes are traversed level by level, where the root node is visited first, followed by its direct child nodes and their siblings, followed by its grandchild nodes and their siblings, etc., until all nodes in the tree have been traversed.
Common operations[edit]
 Enumerating all the items
 Enumerating a section of a tree
 Searching for an item
 Adding a new item at a certain position on the tree
 Deleting an item
 Pruning: Removing a whole section of a tree
 Grafting: Adding a whole section to a tree
 Finding the root for any node
 Finding the lowest common ancestor of two nodes
Common uses[edit]
 Representing hierarchical data such as syntax trees
 Storing data in a way that makes it efficiently searchable (see binary search tree and tree traversal)
 Representing sorted lists of data
 As a workflow for compositing digital images for visual effects^{[citation needed]}
See also[edit]
 Tree structure
 Tree (graph theory)
 Tree (set theory)
 Cardinal Tree and Ordinal Tree
 Hierarchy (mathematics)
 Dialog tree
 Single inheritance
 Generative grammar
 Hierarchical clustering
 Binary space partition tree
 Recursion
Other trees[edit]
 Trie
 Day–Stout–Warren algorithm
 Enfilade
 Left childright sibling binary tree
 Hierarchical temporal memory
Notes[edit]
 ^ Alternatively, a "partial" version can be employed by excluding {r}.
 ^ This would also establish a concordance of the two possible directions of inequality symbols with the categorization of XPath axes into forward axes and reverse axes.
 ^ Properly, a rooted, ordered directed graph.
 ^ This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).
References[edit]
 ^ ^{a} ^{b} Tetsuji Kuboyama (2007). "Matching and learning in trees" (PDF). Doctoral Thesis, University of Tokyo.
 ^ "The Linux VFS Model: Naming structure".
 ^ Bruce Fields. "Notes on the Linux kernel".
 ^ Pierre Cointe (1987). "Metaclasses are First Class: the ObjVlisp Model". Proceeding OOPSLA '87 Conference proceedings on Objectoriented programming systems, languages and applications. NorthHolland.
 ^ Wolfgang Klas, Michael Schrefl (1995). Metaclasses and Their Application: Data Model Tailoring and Database Integration. Springer.
 ^ "What Is a Metaclass?".
 ^ "The Ruby Object Model: Data structure in detail".
 ^ B. Korte, and J. Vygen (2012). Combinatorial optimization. Springer, Heidelberg.
 ^ "XML Path Language (XPath) 3.1". World Wide Web Consortium. 21 March 2017.
 ^ "Document Object Model Traversal". W3C. 2000.
 ^ "Unary Algebras".
 ^ J.T. Mühlberg, G. Lüttgen (2009). "Verifying compiled file system code" (PDF). Formal Methods: Foundations and Applications: 12th Brazilian Symposium on Formal Methods. Springer, Berlin, Heidelberg.
 ^ Weisstein, Eric W. "Subtree". MathWorld.
Further reading[edit]
 Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. AddisonWesley, 1997. ISBN 0201896834 . Section 2.3: Trees, pp. 308–423.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGrawHill, 2001. ISBN 0262032937 . Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, RedBlack Trees, Augmenting Data Structures), pp. 253–320.
External links[edit]
Wikimedia Commons has media related to Tree structures. 
 Data Trees as a Means of Presenting Complex Data Analysis by Sally Knipe in August 8, 2013
 Description from the Dictionary of Algorithms and Data Structures
 CRAN  Package data.tree implementation of a tree data structure in the R programming language
 WormWeb.org: Interactive Visualization of the C. elegans Cell Tree – Visualize the entire cell lineage tree of the nematode C. elegans (javascript)
 Binary Trees by L. Allison