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, represented as a set of linked nodes. A tree data structure can be defined recursively (locally) 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 list 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). A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent.
A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy. A tree can be empty with no nodes called the null or empty tree or a tree is a structure consisting of one node called the root and one or more subtrees.
Terminologies used in Trees
• Root - the top most node in a tree.
• Parent - the converse notion of child.
• Siblings - nodes with the same parent.
• Descendant - a node reachable by repeated proceeding from parent to child.
• Leaf - a node with no children.
• Internal node - a node with at least one child.
• Degree - number of sub trees of a node.
• Edge - connection between one node to another.
• Path - a sequence of nodes and edges connecting a node with a descendant.
• Level - The level of a node is defined by 1 + the number of connections between the node and the root.
• Height - The height of a node is the length of the longest downward path between the
node and a leaf.
• Forest - A forest is a set of n ≥ 0 disjoint trees.