Summary

In this chapter, you learned what a tree is. We started out with an actual implementation and then designed an ADT out of it. You also learned about a binary tree, which is just a tree with a maximum of two children per node. We also saw different traversal algorithms for a generic tree. They are depth-first and breadth-first traversals. In the case of a binary tree, a depth-first traversal can be done in three different ways: pre-order, in-order, and post-order. Even in the case of a generic tree, we can find equivalents of the pre-order and post-order traversals for a depth-first traversal. However, it is difficult to point to any particular equivalent of an in-order traversal as it is possible to have more than two children.

In the next chapter, we will see the use of a binary tree in searching, and we will see some other ways of searching as well.