A binary search tree is a type of binary tree Representing sorted lists of data Computer-generated imagery: Space partitioning, including binary space partitioning Digital compositing Storing Barnes–Hut trees used to simulate galaxies Implementing heaps Nested sets Hierarchical taxonomies such as the Dewey Decimal Classification with sections of increasing specificity. Hierarchical temporal memory Genetic programming Hierarchical clustering Trees can be used to represent and manipulate various mathematical structures, such as: Paths through an arbitrary node-and-edge graph (including multigraphs), by making multiple nodes in the tree for each graph node used in multiple paths Any mathematical hierarchy Tree structures are often used for mapping the relationships between things, such as: Components and subcomponents which can be visualized in an exploded-view drawing Subroutine calls used to identify which subroutines in a program call other subroutines non recursively Inheritance of DNA among species by evolution, of source code by software projects (e.g. Linux distribution timeline), of designs in various types of cars, etc. The contents of hierarchical namespaces JSON and YAML documents can be thought of as trees, but are typically represented by nested lists and dictionaries. Terminology A node is a structure which may contain data and connections to other nodes, sometimes called edges or links. Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn with descendants going downwards). A node that has a child is called the child's parent node (or superior). All nodes have exactly one parent, except the topmost root node, which has none. A node might have many ancestor nodes, such as the parent's parent. Child nodes with the same parent are sibling nodes. Typically siblings have an order, with the first one conventionally drawn on the left. Some definitions allow a tree to have no nodes at all, in which case it is called empty. 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 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