In this chapter
- Understanding size, height, and depth in a tree structure
- Understanding insertion order in the binary search tree
- Traversing trees in various orders
- Implementing the binary search tree
- Merging, folding, and balancing trees
In chapter 5, you learned about the singly linked list, which is probably the most widely used immutable data structure. Although the list is an efficient data structure for many operations, it has some limitations. The main shortcoming is that the complexity of accessing elements grows proportionally with the number of elements. For example, searching for a particular element may necessitate examining all elements if it happens that the searched-for element is the last ...