Trees

A tree data structure is defined as a collection of nodes (starting at the root node), where each node is a data structure consisting of a value and a list of references to nodes (the “children”), with the constraints that there are no duplicate references, and no references point to the root. These references are often referred to as edges. (Trekhleb & Shoemaker, 2019)

As opposed to Linked Lists, which are linear, Trees can have 0 or more child nodes.

What is a node?

A node is a basic unit used in computer science. Nodes are individual parts of a larger data structure, such as linked lists and tree data structures. Nodes contain data and also may link to other nodes. Links between nodes are often implemented by pointers. -Wikipedia24

In tree data structure one node can link to many others, which means that trees can grow in different shapes and ways.

Trees components

  • root node - the topmost node.

  • edge or link - it's a connection between nodes. Parent node contains references to its child nodes.

  • child - any node that has a parent node.

  • parent - any node that has a reference/link to another node.

  • sibling nodes - any group of nodes that are children of the same node.

  • leaf - any node that doesn't have any children in the tree.

References: