1 Basic concepts

Tree structures are hierarchical data models built from individual units connected in a parent-child pattern. They are used to describe relationships in which one item may contain or organize several others. This makes them useful for representing nested categories, directories, and many forms of structured knowledge.

1.1 Nodes and edges

A node is a basic unit of a tree that can store data, while an edge is the link connecting one node to another. In a simple tree, each connection shows a relationship between a parent and a child. Together, nodes and edges define the shape of the structure.

1.2 Root, parent, child, and sibling relationships

The root is the topmost node of a tree and serves as the starting point for navigation. A parent is any node that directly connects to one or more lower nodes, called children. Nodes that share the same parent are siblings.

1.3 Leaves and internal nodes

A leaf is a node with no children, often marking the end of a branch. An internal node has at least one child and functions as a branching point. These categories help describe the overall form of the tree.

1.4 Depth, level, and height

Depth refers to the number of edges from the root to a given node. Level is a related measure that groups nodes according to their distance from the top. Height usually describes the longest path from a node down to a leaf, and for the whole tree it indicates the maximum depth.

1.5 Subtrees

A subtree is a smaller tree formed by a node and all of its descendants. Subtrees preserve the same hierarchical relationships as the larger structure. They are important for analysis, navigation, and recursive operations.

2 Structural properties

Tree structures are distinguished by their branching patterns and the rules that govern how nodes are arranged. These properties affect how easily the tree can be searched, updated, or displayed. Different applications favor different structural choices.

2.1 Hierarchy and branching

Hierarchy is the defining feature of a tree, with each lower level representing a more specific part of the structure. Branching occurs when a node has multiple children, creating new paths in the hierarchy. The branching pattern influences both size and complexity.

2.2 Ordered versus unordered trees

In an ordered tree, the left-to-right sequence of children matters and is part of the structure. In an unordered tree, the children are treated as a set, so their arrangement is not significant. The distinction is important in storage, comparison, and traversal.

2.3 Rooted trees

A rooted tree has a single distinguished root from which all other nodes are reachable. This makes direction and ancestry clear. Rooted trees are the standard form used in most computational settings.

2.4 Balanced and unbalanced forms

A balanced tree keeps its branches at roughly similar depths, which often improves performance. An unbalanced tree has uneven branch lengths and may become long and narrow in some areas. Balance is especially important when fast lookup is desired.

2.5 Degree of a node

The degree of a node is the number of children it has. A node with many children has a higher degree, while a leaf has degree zero. Degree helps describe how much branching occurs at a point in the tree.

3 Common tree types

Many specialized tree forms have been developed for particular tasks. Some emphasize simplicity, while others are designed for efficient search, storage, or text processing. The choice of tree type depends on the problem being solved.

3.1 General trees

A general tree allows each node to have any number of children. It is the most flexible common form and can model broad hierarchical relationships. Because of this flexibility, it appears in many conceptual and software representations.

3.2 Binary trees

A binary tree is a tree in which each node has at most two children, usually called left and right. This restriction makes binary trees especially useful in algorithms and data structures. They are widely studied because many operations can be expressed clearly in this form.

3.2.1 Full binary trees

A full binary tree is one in which every internal node has exactly two children. This creates a regular branching pattern. Such trees are often used in examples and in certain algorithmic contexts.

3.2.2 Complete binary trees

A complete binary tree fills each level as fully as possible from left to right. Only the lowest level may be partially filled. This form supports efficient array-based storage and is commonly associated with heap structures.

3.2.3 Perfect binary trees

A perfect binary tree is completely filled at every level, and all leaves appear at the same depth. This yields a highly regular shape. Perfect trees are useful for theoretical analysis because their size and height follow predictable patterns.

3.3 Multiway trees

A multiway tree permits more than two children per node and is often used when a binary restriction would be too limiting. Such trees appear in indexing, classification, and data organization. They can represent wide branching hierarchies efficiently.

3.4 Trie structures

A trie is a tree used to store strings by shared prefixes. Each step along a path typically corresponds to a character or symbol. Tries are effective for prefix search, spell checking, and dictionary-like tasks.

B-trees are balanced multiway trees designed for efficient storage and retrieval, especially with large datasets. They reduce the number of levels needed for searching by keeping many keys in each node. Related index trees adapt this idea for databases and external storage systems.

4 Traversal and navigation

Traversal methods determine the order in which nodes are visited. Navigation in trees often relies on these methods, along with queries that identify relationships between nodes. Efficient traversal is central to processing hierarchical data.

4.1 Depth-first traversal

Depth-first traversal explores one branch as far as possible before returning to earlier nodes. It is well suited to recursive implementation and to tasks that require complete exploration of a subtree before moving on. This family of methods includes preorder, inorder, and postorder variants.

4.1.1 Preorder traversal

In preorder traversal, a node is visited before its children. This ordering is useful when the structure itself must be recorded before its contents. It is common in copying and serialization tasks.

4.1.2 Inorder traversal

Inorder traversal visits the left child, then the node, then the right child in a binary tree. This order is especially meaningful for binary search trees, where it can produce sorted output. It is less applicable to general trees without a left-right distinction.

4.1.3 Postorder traversal

In postorder traversal, children are visited before the node. This is useful when a parent should be processed only after all dependent parts have been handled. It commonly appears in deletion and evaluation routines.

4.2 Breadth-first traversal

Breadth-first traversal visits nodes level by level, starting at the root and moving across each depth before descending further. It gives a clear view of the tree’s overall shape. This approach is also called level-order traversal.

4.3 Path finding

Path finding in a tree involves identifying the sequence of edges connecting two nodes. Because trees contain no cycles in their simplest form, paths are usually unique. This property simplifies routing, comparison, and ancestry checks.

4.4 Ancestor and descendant queries

An ancestor query asks which nodes lie above a given node along the route to the root. A descendant query examines the nodes below it within the same branch. These queries are fundamental for understanding position and relationship within the hierarchy.

5 Representation and storage

Trees can be stored in several ways depending on performance needs and the nature of the data. Some models emphasize direct linking, while others favor compactness or readability. Representation choices strongly influence how easily a tree can be manipulated.

5.1 Pointer-based representations

In pointer-based representations, each node stores references to its children, and sometimes to its parent. This approach is flexible and supports dynamic insertion and deletion. It is common in in-memory data structures.

5.2 Array-based representations

Array-based representations place nodes into indexed positions, often using arithmetic relationships to locate relatives. This works well for complete or nearly complete binary trees. It can reduce overhead and make access fast.

5.3 Adjacency and nested-list models

Adjacency models record which nodes are connected, often in a compact list form. Nested-list models represent each node together with its children in a nested arrangement. Both approaches are useful when a tree must be stored or transmitted in a readable format.

5.4 Serialization formats

Serialization converts a tree into a linear form that can be saved, transmitted, or reconstructed later. Good serialization preserves structure while remaining concise. It is widely used in file formats, data exchange, and persistent storage.

5.4.1 XML and JSON tree encoding

XML and JSON are common formats for encoding hierarchical data. XML uses nested tags, while JSON often uses arrays and objects to express parent-child relationships. Both are widely supported and easy to interpret programmatically.

5.4.2 Indentation-based outlines

Indentation-based outlines show hierarchy by spacing or line position. A deeper level is visually offset beneath its parent. This method is simple and readable, making it useful for notes, plans, and summaries.

6 Applications in information science

Tree structures are central to many information systems because they organize complex material into manageable layers. They support classification, retrieval, and structured presentation. Their value lies in their ability to model relationships clearly.

6.1 File and folder hierarchies

Operating systems often use trees to organize folders and files. A directory can contain subdirectories and documents, forming a familiar hierarchical layout. This arrangement helps users navigate stored information efficiently.

6.2 Taxonomies and classification systems

Taxonomies arrange subjects into broader and narrower categories. Tree structures are well suited to such systems because they show how general concepts divide into more specific ones. They are used in libraries, databases, and reference works.

6.3 Document outlines and tables of contents

Outlines and tables of contents frequently follow a tree-like structure. Major sections branch into subsections, creating a clear outline of the document. This format helps readers understand organization at a glance.

6.4 Parsing and syntax trees

In parsing, tree structures represent the grammatical organization of text or code. Syntax trees show how tokens combine into phrases or expressions. They are important in language processing and compiler design.

6.5 Search and indexing structures

Search systems often rely on trees to organize keys for rapid lookup. Indexing structures use hierarchical branching to narrow the search space efficiently. This makes them valuable in databases, text retrieval, and related tools.

7 Operations on trees

Tree operations change structure, inspect content, or prepare data for efficient use. Because trees are hierarchical, many operations affect entire branches rather than isolated nodes. Recursive methods are common in this area.

7.1 Insertion and deletion

Insertion adds a new node at an appropriate position, usually as a child of an existing node. Deletion removes a node and may require rearranging nearby parts to preserve structure. The effect depends on the tree type and its rules.

7.2 Searching

Searching locates a node or key within the tree. The process may use traversal, comparison rules, or structural shortcuts. Efficient searching is one of the main reasons for using trees.

7.3 Rebalancing

Rebalancing adjusts the shape of a tree to reduce excessive depth on one side. This can improve performance for lookup and update operations. Balanced maintenance is especially important in ordered search trees.

7.4 Merging and splitting

Merging combines two trees into one larger structure, often under a new root or within a shared framework. Splitting divides a tree into separate parts, each with its own hierarchy. These operations appear in storage systems and algorithmic processing.

7.5 Copying and cloning

Copying creates a duplicate tree with the same arrangement and stored values. Cloning may preserve structure while producing an independent version. These operations are useful when a tree must be reused without altering the original.

Several structures are closely connected to trees but differ in one or more important ways. Some remove the single-root constraint, while others allow additional links or specialized behavior. These variants broaden the usefulness of hierarchical models.

8.1 Forests

A forest is a collection of separate trees. It is often used when multiple hierarchies exist side by side. Forests arise naturally after removing a root from a tree.

8.2 Directed acyclic graphs

A directed acyclic graph contains directed edges and no cycles, but unlike a tree, a node may have multiple parents. This allows shared substructure and more compact representation in some cases. It is more flexible than a tree, though also more complex.

8.3 Heaps

A heap is a tree-based structure that follows a special ordering rule between parent and child nodes. It is commonly used to manage priority-based access. Heaps are especially important in scheduling and selection algorithms.

8.4 Segment trees

A segment tree is a hierarchical structure used to store information about intervals or ranges. It supports efficient queries and updates over contiguous sections of data. This makes it useful in computational problems involving ranges.

8.5 Decision trees

A decision tree models a sequence of choices, with branches representing alternative outcomes. Each path from the root leads to a result or classification. Decision trees are used in analysis, pattern recognition, and rule-based systems.