Trees are data structures that follow a hierarchy, each node has exactly one or zero parents and each node has children. Trees are recursive structures meaning that each child of a tree is also a tree. A tree within another tree is called a subtree.
A child is a node that is below another node.
A parent is a node that is above another node.
The element at the top of the tree with no parents is called a root. The node at the bottom of the tree with no children is called a leaf.
Each node can hold different kinds of information depending on the tree. A node can hold the children it has, the parent it has, a key associated with the node and a value associated with the node.
- A is the root of the tree and E,F,G,H are leaves.
- The parent of E is B.
- C,F,G is a subtree of the original tree.
A binary tree is a tree where every node has at max two children.