Graphs and trees

Graphs and trees are considered non-linear data structures, which come in handy in solving various kinds of problems. Though they are both non-linear data structures, they have differences, which help us distinguish them from each other. For example, the tree should have a root node, while the graph doesn’t have one; the tree forms a tree-like structure when dealing with data while the graph organizes the data into a network-like structure; there can be loops in a graph, while a tree doesn’t allow this; and so on.

Trees

Thinking about a combination of a binary search algorithm and sorting algorithms can lead to the idea of having a container that maintains objects so that they’re sorted by default. std::set, which is built on a balanced tree, is one such container. Before discussing balanced trees, let’s look at the binary search tree, which is a great option for quick lookups.

The binary search tree’s concept is that the...