Tree

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.
• Width:
• Balance:

Types of Trees

Binary trees

There are a few types of binary trees.

• Perfect
• Full
• Complete
• Binary search tree

In a perfect binary tree, the number of nodes is log(height + 1).

Traversing Trees

• 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.