Get startedGet started for free

Trees and graphs

1. Trees and graphs

In this video, we will study two data structures: trees and graphs.

2. Trees - definition

Let's start by defining trees. Trees are node-based data structures where each node can have links to more than one node.

3. Trees - terminology

The first node of a tree is called the root. A node

4. Trees - terminology

can be the parent

5. Trees - terminology

of other nodes. These nodes are called children.

6. Trees - terminology

Trees have levels. In this tree,

7. Trees - terminology

we have these four levels.

8. Trees - binary tree

Let's introduce a special kind of tree. It is the binary tree. A binary tree is a tree in which each node has zero, one, or two children.

9. Trees - binary tree implementation

This code shows the implementation of a TreeNode in a binary tree. With it, we can set the value for the node, the value for the left_child, and the value for the right_child. We can build a tree like this one with this code.

10. Trees - real uses

Trees have many applications in storing hierarchical relationships, such as the file system of a computer, or the structure of an HTML document. Trees are also used in chess to store the possible moves that a rival player can make. And in general, trees appear in many searching and sorting algorithms.

11. Graphs

A graph is a data structure formed by a set of nodes, also called vertices. The nodes are connected by links, also called edges. The following graph can represent a social network, where nodes represent persons and edges represent the friendship between the persons. Trees are a type of graph.

12. Graphs - types

Graphs can be directed when they have one specific direction. For example, in this social network, David follows Martin, but Martin doesn't follow David.

13. Graphs - types

Graphs can also be undirected when their edges have no direction. In this case, we assume the relationship is mutual. For example, we can model the friendship between Ben and Daya with undirected links, assuming that both are friends.

14. Graphs - types

Weighted graphs have numeric values associated with the edges. These graphs can be either directed or undirected. The following weighted graph represents the distance between different cities.

15. Graphs vs. trees

Let's see the differences between trees and graphs. Trees cannot have cycles. It means that the nodes cannot reference each other circularly, while graphs can have cycles. In a tree, all the nodes must be connected, while in graphs, there can be

16. Graphs vs. trees

unconnected nodes.

17. Graphs - real world use-cases

Graphs can represent the user relationships in social networks, like the friendship between two users, if a user follows another user, the likes, etc. Graphs can also represent locations and distances between these locations. With this information, we can optimize the routes. Graph databases use graphs to store the information that is consumed by lots of applications. As trees, graphs appear in many searching and sorting algorithms.

18. Graphs - implementation

Graphs can be implemented as follows. The graph will have a dictionary to store all the vertices. Vertices can be added with the add_vertex method, and edges with the add_edge method. We can build a graph like this one with this code, using the add_vertex and add_edge methods. We can print the vertices to check the content. Instead, we can use adjacency matrices, but these last are out of the scope of this course.

19. Let's practice!

Let's get to know trees and graphs better with some exercises!