What is a tree?

A tree is a connected, undirected graph with no cycles. A tree may have a root node – known as a rooted tree – or no identifiable root node. Unlike a graph, a rooted tree is often used to define parent-child relationships between nodes and store hierarchical data.

There are many different types of tree structures including general trees, AVL trees, b-trees, binary trees, binary interval trees, cartesian trees, KD trees, search trees, quad trees, R-trees, red-black trees, splay trees, and treaps to name a few. For the purposes of examinations, it is sufficient for you to only understand the similarities and differences between general trees and binary search trees.

Unlike a binary tree, a general tree is not limited to a maximum of two child nodes. A node can have any number of children, but loops between nodes are not permitted and it is common for one node to have a single parent. Therefore, there is only one path to any one node.