Tree (abstract data type)

In computer science a tree is a widely used abstract data type that represents a hierarchical structure made of connected nodes. Every node can have many children, depending on the kind of tree, but exactly one parent, except the topmost root node, which has none. These constraints rule out cycles, and they mean each child can be treated as the root of its own subtree, which makes recursion a natural way to walk a tree. Binary trees, which allow at most two children per node, are a common special case. A tree can be stored as a list of parents with pointers to children, a list of children with pointers to parents, or a list of nodes with a separate list of parent and child relations. Common operations include enumerating items, searching, adding or deleting an item, pruning a section, grafting a section and finding the lowest common ancestor of two nodes.