Recursion and Trees

This chapter is about trees. A tree is a linked structure defined recursively: a node holding a value, with zero or more smaller trees beneath it that branch apart and never rejoin.

After reading this chapter, you should be able to:

  • Draw the call tree of a recursive run, and tell a chain (one recursive call) from a branching tree (several)
  • Give recursive definitions of a linked list, a tree, and a binary tree
  • Identify the parts of a tree, such as the root, children, leaves, and subtrees
  • Represent a binary tree with Node objects and write recursive methods over it, such as size, height, and depth
  • Write and trace the recursive pre-order, in-order, and post-order traversals of a binary tree
  • Explain why a recursive traversal produces only depth-first orders
  • Implement level-order traversal with a queue
  • Choose a traversal order to fit a task on a tree

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. Revisiting Recursion
  2. The Call Tree
  3. A Linked List Is Recursive
  4. A Tree Is Recursive
  5. Linked Lists and Trees
  6. Anatomy of a Tree
  7. Narrowing to Binary Trees
  8. From a Definition to a Node
  9. Counting the Nodes
  10. Measuring Height
  11. Measuring Depth
  12. Traversing the Tree
  13. Tracing the Three Orders
  14. Traversing Level by Level
  15. Trying Recursion
  16. A Queue of Waiting Nodes
  17. Level-order in Code
  18. Traversals in Practice