Tree (data structure)

In computer science, a tree is a graph data structure composed of items called nodes. These nodes can point to other nodes, known as child nodes, or children.^[1] Usually, a tree is read from top to bottom.

Every tree has a node known as a root node. The root node does not have a node that points to it, but it can point to other nodes. In other words, no node has the root as a child.

The thing that makes trees different from a normal graph data structure is that trees may not have cycles. This means that between any two nodes, there can only exist one path between the nodes. If there was more than one path, the structure would just be a graph data structure.

A node is known as a leaf if it has no children. The bottom of a tree structure will usually be the place with the most leaves. The height of a node is the length of the longest path from a specific node to a leaf below that node.^[2] The height of the root is also known as the height of a tree. The height of the root would be determined by the length of the longest path from the root of a tree to a leaf of that tree. ^[3] The depth of a node is the length of the path from the tree's root to that node.^[4]