More about binary trees

Now that you know how to work with BST, you can dive into the study of trees if you would like to.

BST has an problem: depending on how many nodes you add, one of the edges of tree can be very deep, meaning a branch of the tree can have a high level, and another branch can have a low level, as shown in the following diagram:

This can cause performance issues when adding, removing, and searching for a node on a particular edge of the tree. For this reason, there is a tree called Adelson-Velskii and Landis' tree (AVL tree). The AVL tree is a self-balancing BST tree, which means the height of both the left and right subtree of any node differs by 1 at most. This means the tree will try to become a complete tree whenever possible while adding or removing a node.

We will not cover AVL trees in this book, but you can find its source code inside the chapter08 folder of this book's source code and take a look at it there.

Note

Another tree that you should also learn about is the...