A tree is a data structure used for storing data. It is based on the mathematical tree, which is defined as a simple connected undirected acyclic graph. Trees in computer science represent a simple connected directed acyclic graph, where the origin of operations start with the root node.

Trees are especially efficient in the searching of sorting lists, as opposed to linked lists, which require strict sequential access. Trees are also important in some applications that require specifically the tree data structure.

Trees are made up of items known as nodes (equivalent to vertices in graphs). As in linked lists, nodes typically consists of pieces of useful data and one or more pointers to its children nodes.

Operations

Depending on the specific implementation, a tree may have different operations that may be done with it.

Traversal

Traversal is a means of listing all the nodes in a tree.

• breadth-first traversal: the nodes are traversed by level starting from the root node.
• preorder or depth-first traversal: In binary trees, the nodes are traversed using a recursive algorithm: start with the root node of the tree, then traverse its left subtree, then traverse its right subtree.
• inorder or symmetric traversal: Starts with the left subtree, then the root node, then the right subtree.
• postorder traversal: Starts with the left subtree, then the right subtree, then the root node.

See also

• Heap
• Binary tree