AI Glossary / Data engineering and architecture / Beginner
Tree (abstract data type)
Definition
A tree is an abstract data type for organizing items in a hierarchy. In a non-empty rooted tree, one node is the root, and every other node has exactly one parent. Nodes may have children, and the structure contains no cycles. The abstract data type describes the relationships and supported operations without requiring a particular implementation.
What it means
A node represents an item, while a parent-child connection represents its place in the hierarchy. A node with no children is a leaf. Nodes sharing a parent are siblings, and a node together with its descendants forms a subtree.
Different tree variants impose additional rules. A general tree permits varying numbers of children; a binary tree allows at most two, usually distinguished as left and right. An ordered tree gives meaning to the order of children. Some definitions allow an empty tree. These details should be specified by the interface rather than inferred from a diagram alone.
How it works
A tree interface commonly supports accessing the root, examining a node's value and children, and navigating or modifying relationships. The implementation might store links between node records, arrays of child references or another representation. Those choices affect performance without changing the intended hierarchy.
Traversal visits nodes in a defined order. Preorder visits a node before its descendants; postorder visits its descendants before the node. The order among siblings matters when the tree is ordered. Applications choose a traversal that suits their task, such as displaying a hierarchy or combining child results.
Updates must preserve the tree's rules. Moving a subtree beneath one of its own descendants would create a cycle. Assigning the same node two parents would create a different kind of structure unless the application deliberately represents separate copies.
Three practical examples
1. Document outline: A report contains sections, subsections and paragraphs. A tree can represent their containment and order so that editing and display preserve the document's structure.
2. Category navigation: A catalog uses a single-parent category hierarchy. If products can belong to several categories, their membership needs a separate relationship rather than pretending every product has one unique parent category.
3. Expression processing: A system represents an expression through operation nodes and operand nodes. A traversal can evaluate child expressions before combining their results at the parent operation.
Think of it this way
Think of an outline with one top-level title, nested headings and subordinate bullet points. Each item belongs beneath a specific parent, and its indentation shows the hierarchy.
The analogy has limits. Real information often includes cross-references, shared ownership or multiple reporting relationships that do not form a pure tree. A tree representation is useful only if its single-parent structure matches the relationship being modeled. Visual indentation alone cannot prove that the underlying data has no cycles or shared nodes.
Worked example
Suppose a document tree has root R with ordered children A and B. A has children C and D, while B has child E. There are six nodes and five parent-child edges.
A preorder traversal produces R, A, C, D, B, E: each parent appears before its children. A postorder traversal produces C, D, A, E, B, R: child subtrees are completed before their parent. The same tree therefore supports different processing orders without changing its contents.
Now attempt to move A beneath C. Since C is already inside A's subtree, this would create the cycle A - C - A. A valid move operation must reject it or use different, explicitly defined semantics. Checking only that C exists is insufficient; the operation must also check the relationship between the source subtree and proposed destination.
Illustrative case study
Fictional case study: BranchMeadow builds a training-content catalog. It initially models every lesson as a child of exactly one course, which makes course outlines easy to display. Later, editors want one lesson to appear in several courses while retaining a single editable lesson record.
The team separates lesson identity from course placement. Each course outline remains a tree of placement nodes, and those nodes reference shared lesson records stored outside the outline. Editing a lesson changes its content without giving one tree node several parents.
BranchMeadow learns to distinguish the hierarchy of appearances from the identity of reusable content. This avoids silently changing a tree into a general graph while preserving the editing behavior the business actually needs.
Common misconceptions and mistakes
A common mistake is assuming that every tree is a binary search tree. A general hierarchy has no automatic ordering by key and no universal logarithmic search guarantee. Another is mistaking a drawing with several levels for proof that the data obeys tree constraints.
Do not confuse a tree data structure with a trained decision-tree model, although such models use tree-shaped structures. Also distinguish a node from its displayed label. Two nodes can have the same text while representing different items; merging them solely because their labels match can corrupt the hierarchy.
Business use
Trees support navigation, structured documents, parsing and many forms of hierarchical organization. Choosing a clear tree interface can separate business meaning from implementation details and make operations easier to reason about.
For data and AI projects, verify whether the modeled relationship truly has one parent per item. Taxonomies, document sections and expression structures may fit, while social relationships or shared dependencies may require graphs. Useful checks include root handling, unreachable nodes, accidental cycles, duplicate identities and valid subtree moves. Performance testing should reflect actual operations and tree shape rather than assume all trees remain shallow or balanced.
People also ask
Must every node have two children?
No. That is a restriction associated with binary trees, and even a binary-tree node can have fewer than two children.
Can two nodes have the same value?
Yes, unless the particular interface or application imposes uniqueness. Node identity and stored value are different concepts.
Is every hierarchy naturally a tree?
No. Multiple parents or cyclic relationships require a different representation or a carefully defined tree view of the underlying information.
Check your understanding
A node is given a second parent while its first parent connection remains. Does the structure still satisfy the rooted-tree definition?
Answer: No. Every non-root node must have exactly one parent. Shared content can instead be represented through separate placement nodes or a graph model.
Related terms
Learn next
Build a six-node hierarchy and write its preorder and postorder sequences. Then test a subtree move that should succeed and one that would create a cycle.
More in Data engineering and architecture
- Transitive Dependency - A transitive dependency is an indirect functional dependency obtained through an intermediate attribute set.
- Transitive Rule - The transitive rule is an inference rule for functional dependencies in relational database theory. If X → Y and Y → Z hold, then X → Z also holds.
- Traversed edges per second - Traversed edges per second, or TEPS, is a performance rate used to describe graph-processing work.
- Tree contraction - Tree contraction is an algorithmic technique that repeatedly reduces a tree to a smaller structure while preserving information needed to solve a problem.
- Trivial Functional Dependency - A trivial functional dependency is a dependency X → Y in which every attribute of Y is already included in X.
- Trivial MVD - A trivial multivalued dependency, or trivial MVD, is a multivalued dependency X →→ Y that holds automatically because Y is contained in X, or because X...
Sources
NIST Dictionary of Algorithms and Data Structures, “tree”: https://xlinux.nist.gov/dads/HTML/tree.html
OpenDSA, general trees and their abstract data type: https://opendsa-server.cs.vt.edu/ODSA/Books/pubbook/odsa-all/fall-2019/Public_Instance/html/GenTreeIntro.html
These sources support tree terminology and operations. The document traversal and BranchMeadow case are fictional illustrations; application-specific ordering and empty-tree rules should be stated explicitly.
Previous: Treatment effect Next: Tree-based feature selection