A tree is a recursive data structure with a single root node and zero or more child nodes. It is also a special case of graph. Each link between a node is called an edge.
Properties of trees
- Depth of a node: The number of edges between the node and the root node.
- Height: The number of edges between the root node and the furthest leaf node. This is the same as the depth of the furthest leaf node.
Types of Trees
There are a few types of binary trees.
- Binary search tree
In a perfect binary tree, the number of nodes is
log(height + 1).
- In order: Visits left child, current node, then right child. It is called "In order" because in a binary search tree, this would visit each node in order.
- Pre order: Visits current node, left child, right child.
- Post order: Visits left child, right child, current node.