10 More data handling with trees

This chapter introduces binary trees as an immutable, recursive alternative to singly linked lists for faster search, selection, and ordered traversal. It explains core concepts—nodes with left and right branches, subtrees, leaves, and the formal treatment of empty trees—along with the distinctions between size, height, and depth. It then specializes to binary search trees, where left values are less than the root and right values are greater, eliminating duplicates and enabling logarithmic-time search when balanced. The chapter shows how insertion order shapes the tree’s structure, why pre-ordered data can degenerate a BST into a list, and surveys traversal strategies (pre-, in-, and post-order depth-first, plus level-first breadth-wise) and their practical implications for processing.

The implementation section models a generic, persistent BST in Kotlin with a sealed Tree type and two variants (non-empty and empty), addressing variance constraints with Comparable and the judicious use of @UnsafeVariance. It develops the key operations needed for a usable immutable set: insertion via a plus operator, construction from lists/arrays, membership testing, and efficient size and height as memoized properties. It adds min/max (safely via a Result type), element removal using a branch-aware merge, and a general merge for arbitrary trees that respects ordering while collapsing duplicates. Throughout, the chapter discusses recursion depth, operator overloading, and how immutability drives reconstructing new trees while sharing unchanged substructures.

Beyond basics, the chapter explores folding trees: combining subtree results with either two functions (to fold and to merge partial results) or single-function variants tailored to pre-, in-, or post-order traversals. It shows how to reconstruct an original tree from folds using a smart constructor that preserves BST ordering when possible, enabling mapping that retains structure for order-preserving functions. The final part focuses on balancing: local rotations (left/right), producing in-order lists in a stack-safe way, and applying the Day–Stout–Warren algorithm to transform any tree into a well-balanced one near the optimal height. A practical strategy for auto-balancing is proposed—triggering balancing heuristically after mutations—to maintain performance and avoid stack overflows without incurring excessive rebalancing cost.

Figure 10.1. A binary tree is a recursive structure composed of a root and two branches. The left branch is a link to the left subtree, and the right branch is a link to the right subtree. Terminal elements have empty branches (not represented in the figure) and are called leaves.

Figure 10.2. Trees can be more or less balanced. The top tree is perfectly balanced because the two branches of all subtrees contain the same number of elements. Perfectly balanced binary trees are sometimes called perfect trees. The tree on the right is a singly linked list, which is a special case of a totally unbalanced tree.

Figure 10.3. A leafy tree holds values only in the terminal nodes, which are called leaves

Figure 10.4. An example of an ordered tree, or binary search tree (BST). All elements in one branch (by convention, the left branch) have a lower value than the root element, and all elements in the other branch (again, by convention, the right branch) have a higher value than the root element. The same traits apply to all subtrees.

Figure 10.5. Many different insertion orders can give the same tree. A set of ten elements can be inserted into a tree in 3,628,800 distinct orders, but this will only produce 16,796 distinct trees. These trees will range from perfectly balanced to totally unbalanced. Ordered trees are very efficient for storing and retrieving random data, but they’re very bad at storing and retrieving pre-ordered data.

Figure 10.6. Depth-first traversal consists in traversing the tree while giving priority to height. There are three main orders in which this may be applied.

Figure 10.7. Level-first traversal order consists in visiting all the elements of a given level before going to the next level.

Figure 10.8. The two trees to be merged. On the left is this tree, and on the right is the parameter tree.

Figure 10.9. The root of the parameter tree is higher than the root of this tree. Merge the right branch of this tree with the parameter tree with its left branch removed. (The merging operation is represented by the dotted box.)

Figure 10.10. The roots of each tree to be merged being equal, you use this value for the result of the merge. The left branch will be the result of merging the two left branches, and the right branch will be the result of merging the two right branches.

Figure 10.11. For the left branch, merging with an empty tree is trivial and just returns the original tree (root 4 and two empty branches). For the right branch, the first tree has empty branches and 6 as its root, and the second tree has 7 as its root, so you remove the left branch of the 7 rooted tree and use the result to merge with the empty right branch of the 6 rooted tree. The removed left branch will be merged with the result of the previous merge. Note that the 6 rooted tree on the right comes from the 7 rooted tree, where it has been replaced by an empty tree.

Figure 10.12. The two trees to be merged have equal roots (6) so you merge the branches (left with left and right with right). As the tree to be merged has both branches empty, there is in fact nothing to do.

Figure 10.13. Merging an empty tree simply results in the tree to be merged. You’re left with two trees with the same root to merge.

Figure 10.14. Merging two trees with the same root is simple: just merge right with right and left with left, and use the results as the new branches.

Figure 10.15. The left merge is trivial because the roots are equal and both branches of the tree to be merged are empty. On the right side, the tree to be merged has a lower root (4), so you remove the right branch (E) and merge what remains with the left branch of the original tree.

Figure 10.16. Merging two identical trees doesn’t need any explanation.

Figure 10.17. The final result after merging the last empty tree.

Figure 10.18. Reading the tree from left to right and from right to left. Although both lists are in different orders, they represent the same tree.

Figure 10.19. Rotating a tree to the right. During the rotation, the line between 2 and 3 is replaced with a line between 2 and 4, so element 3 is moved to become the left element of 4.

Figure 10.20. Rotating a tree to the left. The left element of 6 becomes 4 (formerly the parent of 6) so the 5 is moved to become the right element of 4.

• Trees are recursive data structures in which one element is linked to one or several subtrees. In some trees, each element (sometimes called a node) may be linked to a variable number of other elements. Most often, though, they’re linked to a fixed number of elements.
  
• In binary trees, each element is linked to two elements. Those links are called branches, and those branches are called the left and right branches. Binary search trees allow much faster retrieval of comparable elements.
  
• Trees may be more or less balanced. Fully balanced trees provide the best performance, whereas totally unbalanced trees have the same performance as lists.
  
• The size of a tree is the number of elements it contains; its height is the longest path in the tree.
  
• The tree structure depends upon the order of insertion of the tree elements.
  
• Trees can be traversed in many different orders (pre order, in order, post order), and in both directions (left to right, or right to left).
  
• Trees can be easily merged without traversing them.
  
• Trees can be mapped or rotated, as well as folded, in many ways.
  
• Trees can be balanced for better performance and to avoid stack overflow in recursive operations.
  

FAQ