Chapter 6. Binary Trees: Infinity in the Palm of Your Hand

Getting Started

Linked lists and arrays store information in a linear arrangement. In this chapter, I introduce the binary tree recursive data structure, one of the most important concepts in the field of computer science. In Chapter 5, you learned about the concept of recursion, where a function calls itself. In this chapter, you will learn that the binary tree is a recursive data structure—that is, it refers to other binary tree structures. To introduce the concept of a recursive data structure, let’s revisit the linked list data structure you have already seen.

A linked list is an example of a recursive data structure because each node has a next reference to the first node of a sublist. Linked lists improve upon fixed-length arrays by supporting dynamic growth and reduction of a collection of N values. The sum_list() recursive function, shown in Listing 6-1, processes a linked list to return its sum. Compare its implementation against a traditional iterative solution.

Listing 6-1. Recursive and iterative functions to sum the values in a linked list
class Node:
  def __init__(self, val, rest=None):
    self.value = val
    self.next = rest

def sum_iterative(n):
  total = 0                         1
  while n:
    total += n.value                2
    n = n.next                      3
  return total

def sum_list(n):
  if n is None:                     4
    return 0
  return n.value + sum_list(n.next) 5
1

Initialize total to 0 to prepare for computation.

2

For each node, n, in linked list, add its value to total.

3

Advance to the next node in the linked list.

4

Base case: the sum of a nonexistent list is 0.

5

Recursive case: the sum of a linked list, n, is the sum of its value added to the sum of the rest of the list.

The while loop visits each node in the linked list and accumulates a running total of all values stored by nodes in the list. In contrast, sum_list() is a recursive function with a base case that terminates the recursion and a recursive case that composes results of smaller problem instances together. In the base case, the sum of a nonexistent list is 0. If a list, n, has at least one node, then the recursive case computes the sum of the rest of the list (that is, the list starting with n.next) and adds that result to n.value to determine the total sum.

A linked list of N nodes is recursively decomposed into a first node, n, and the rest, a sublist containing N – 1 nodes. This is a recursive decomposition—since, by definition, the rest is a sublist—but it only subdivides the problem of size N (i.e., find the sum of the values contained in N nodes) into a smaller problem of size N – 1 (i.e., find the sum of the values contained in N – 1 nodes). To envision a recursive data structure that has more productive subdivisions, consider representing basic mathematical expressions using binary operations, such as multiplication. A valid expression is either a value or combines two sub-expressions using a binary operation:

  • 3 — any numeric value is valid

  • (3 + 2) — add a left value 3 with a right value 2

  • (((1 + 5) ∗ 9) – (2 ∗ 6)) — subtract a right expression (2 ∗ 6) from a left expression ((1 + 5) ∗ 9)

Expressions can combine and grow to be as large as desired—the expression in Figure 6-1 has seven mathematical operations and eight numeric values. Linked lists cannot model this non-linear expression. If you’ve ever tried to visualize genealogies using family trees, then you can see why the diagram is called an expression tree.

Mathematical Expressions
Figure 6-1. Representing mathematical expressions using expression trees

The top multiply node has two child nodes, ultimately leading to four grandchild nodes (one of which is the value 4), six great-grandchild nodes, and two great-great grandchild nodes.

The expression in Figure 6-1 represents the multiplication of two expressions, which demonstrates its recursive structure. To compute the value of this expression, first recursively compute the left expression to produce the result 1. In similar recursive fashion, the right expression evaluates to 42, so the overall result of the original expression is 1 ∗ 42 = 42.

Figure 6-1  visualizes  the  recursive  substructures  of  the  original  expression.  At  the  top  is  a  box  representing  a  multiplication  expression,  with  a  left  arrow  and  a  right  arrow  to  its  left  and  right  sub-expressions.  Each  circle  represents  a  Value  node  containing  a  numeric  value,  providing  the  base  cases  that  stop  recursion.  The  Expression  data  structure  in Listing 6-2  models  expressions  using  left  and  right  sub-expressions.

Listing 6-2. Expression data structure to represent mathematical expressions
class Value:                                    1
  def __init__(self, e):
    self.value = e

  def __str__(self):
    return str(self.value)

  def eval(self):
    return self.value

class Expression:                               2
  def __init__(self, func, left, right):
    self.func  = func
    self.left  = left
    self.right = right

  def __str__(self):                            3
    return '({} {} {})'.format(self.left, self.func.__doc__, self.right)

  def eval(self):                               4
    return self.func(self.left.eval(), self.right.eval())

def add(left, right):                           5
  """+"""
  return left + right
1

A Value stores a numeric value. It can return its value and string representation.

2

An Expression stores a function, func, and left and right sub-expressions.

3

Provides built-in __str()__ method to recursively produce strings with parentheses around expressions.

4

Evaluate an Expression by evaluating left and right children and passing those values to func.

5

Function to perform addition; mult() for multiplication is similar. The docString __doc__ for the function contains the operator symbol.

Evaluating an Expression is a recursive process that will eventually terminate at Value objects. Using the same technique I introduced in Chapter 5, Figure 6-2 visualizes the recursive evaluation of the expression m = ((1 + 5) ∗ 9):

>>> a = Expression(add, Value(1), Value(5))
>>> m = Expression(mult, a, Value(9))
>>> print(m, '=', m.eval())
((1 + 5) * 9) = 54

To evaluate m, there could be up to two recursive calls, one on the left and right sub-expressions, respectively. In this case, the left sub-expression, a = (1 + 5) is evaluated recursively, while the right sub-expression, 9, is not. The final computation of 54 is returned as the final result. This example demonstrates the usefulness of the Expression recursive binary tree data structure. It also shows that recursive implementations are brief and elegant.

It is critical that recursive data structures have no structural defects. For example:

>>> n = Node(3)
>>> n.next = n           # This is dangerous!
>>> print(sum_list(n))
RecursionError: maximum recursion depth exceeded

This linked list is defined by a node, n, whose next node in the linked list is itself! There is nothing wrong with the sum_list() function—the linked list has a structural defect and so the base case for sum_list(n) never occurs. A similar situation could occur in an Expression. These defects are programming mistakes and you can avoid them by carefully testing your code.

Recursive evaluation
Figure 6-2. Visualizing recursive evaluation of ((1 + 5) ∗ 9)

Binary Search Trees

Binary trees are the godfather of all recursive data structures. A binary search tree can store collections of values with efficient search, insert, and remove operations.

Storing values in a sorted array is necessary for Binary Array Search to provide O(log N) performance. There are countless other reasons to produce information in sorted order to make it easier for users to view information. From a practical standpoint, very large fixed arrays are challenging because they require contiguous memory that must be allocated by the underlying operating system. In addition, changing the size of the array is problematic:

  • To add a new value to an array, a new and larger array is created, and values from the old array are copied into the new array—while making room for the new value. Finally, memory for the old array is released.

  • To remove a value from the array, all values to the right of the removed value must shift one index location to the left. The code must remember that there are “unused” index locations at the end of the array.

Python programs avoid these difficulties because the built-in list structure can already grow and shrink without programmer effort, but in the worst case, inserting a value into a Python list remains O(N). Table 6-1 measures the runtime performance both when prepending 1,000 values (one at a time) to the front of a list of size N, and when appending 1,000 values (one at a time) to the end of a list of size N.

Table 6-1. Comparing insert and remove performance of lists against binary search tree (time in ms)
N Prepend Append Remove Tree

1,024

0.07

0.004

0.01

0.77

2,048

0.11

0.004

0.02

0.85

4,096

0.20

0.004

0.04

0.93

8,192

0.38

0.004

0.09

1.00

16,384

0.72

0.004

0.19

1.08

32,768

1.42

0.004

0.43

1.15

65,536

2.80

0.004

1.06

1.23

131,072

5.55

0.004

2.11

1.30

262,144

11.06

0.004

4.22

1.39

524,288

22.16

0.004

8.40

1.46

1,048,576

45.45

0.004

18.81

1.57

As you can see in Table 6-1, the time to append values to the end of a list is constant at 0.004; this can be considered the best case for inserting values into a list. The time to prepend 1,000 values to the front of a list essentially doubles when the size of the problem instance, N, doubles. This operation can be classified as O(N). This table demonstrates the hidden cost of using a list to maintain a collection of sorted values. The column labeled “Remove” in Table 6-1 reveals that removing the first value from a list 1,000 times is O(N) too, since its runtime performance doubles as N doubles. Each successive value in this column is almost exactly twice as large as the value above it.

Tip

If the performance of inserting a value 1,000 times is O(N), you know that the performance of inserting a single value is also O(N), using the reasoning I introduced in Chapter 2. Inserting 10,000 values is O(N) using the same reasoning, since these behaviors are all just a multiplicative constant different from each other.

This empirical trial reveals O(N) performance when simply inserting or removing a value; maintaining the array in sorted order will only slow the program down. In contrast, the column labeled “Tree” in Table 6-1 reports the runtime performance when using a balanced binary search tree to maintain the collection of values while inserting 1,000 new values. As the problem size doubles, the runtime performance appears to increase by a constant amount, which is characteristic of O(log N) performance. Even better, the binary search tree provides efficient search, insert, and remove operations.

Figure 6-3 contains an example of a binary search tree placed side by side with a sorted array containing the same values. This is the same array from Figure 2-5, where I presented Binary Array Search. The top node in a binary tree is designated as the root of the tree, analogous to how the first node in a linked list is specially designated. In total there are seven nodes in this tree.

Recursive evaluation
Figure 6-3. Binary search tree containing seven values

Each node in the binary search tree has the structure defined in Listing 6-3. left refers to a node that is the root of its own subtree; the same is true of right. A binary search tree adds two global constraints for each node, n, in the tree:

  • If a node, n, has a left subtree, all values in the subtree are ≤ n.value.

  • If a node, n, has a right subtree, all values in the subtree are ≥ n.value.

You can confirm these properties hold in Figure 6-3. A leaf node is a node without a left or right subtree; there are four leaf nodes in this tree, containing the values 3, 15, 26, and 58. Many people have commented that computer science trees are upside down, because the leaves are at the bottom, while the root is at the top.

Listing 6-3. Structure of a binary search tree
class BinaryNode:
  def __init__(self, val):
    self.value = val             1
    self.left  = None            2
    self.right = None            3
1

Each node stores a value.

2

Each node’s left subtree, if it exists, contains values ≤ value.

3

Each node’s right subtree, if it exists, contains values ≥ value.

Referring  back  to  Figure 6-3,  you  can  see  how  the  left  subtree  of  the  root  node  is  itself  a  tree  whose  root  node,  14,  has  a  left  leaf  node  (representing  3)  and  a  right  leaf  node  (representing  15).  These  are  exactly  the  same  values  in  the  array  depicted  on  the  right  that  are  smaller  than  or  equal  to  19,  the  middle  index  in  the  array.  A  binary  tree  grows  top  to  bottom  as  values  are  inserted,  one  at  a  time,  as  shown  in  Table 6-2.

Table 6-2. Creating a binary search tree by inserting (in order) 19, 14, 15, 53, 58, 3, and 26
Grow Tree 1

To insert 19, create a new subtree with root of 19.
Grow Tree 2

To insert 14, 14 is smaller than or equal to 19, so insert 14 into the left subtree of 19, but there is no left subtree, so create a new subtree with root of 14.
Grow Tree 3

To insert 15, 15 is smaller than or equal to 19, so insert 15 into the left subtree of 19 rooted at 14. Now 15 is larger than 14, so insert 15 into the right subtree of 14, but there is no right subtree, so create a new subtree with root of 15.
Grow Tree 4

To insert 53, 53 is larger than 19, so insert 53 into the right subtree of 19, but there is no right subtree, so create a new subtree with root of 53.
Grow Tree 5

To insert 58, 58 is larger than 19, so insert 58 into the right subtree of 19 rooted at 53. Now 58 is larger than 53, so insert 58 into the right subtree of 53, but there is no right subtree, so create a new subtree with root of 58.
Grow Tree 6

To insert 3, 3 is smaller than or equal to 19, so insert 3 into the left subtree of 19 rooted at 14. Now 3 is smaller than or equal to 14, so insert 3 into the left subtree of 14, but there is no left subtree, so create a new subtree with root of 3.
Grow Tree 7

To insert 26, 26 is larger than 19, so insert 26 into the right subtree of 19 rooted at 53. Now 26 is smaller than or equal to 53, so insert 26 into the left subtree of 53, but there is no left subtree, so create a new subtree with root of 26.

It is convenient to have a BinaryTree class to maintain the reference to the root node for a binary tree; over time in this chapter, additional functions will be added to this class. Listing 6-4 contains the code needed to insert values into a binary search tree.

Listing 6-4. BinaryTree class to improve usability of binary search tree
class BinaryTree:
  def __init__(self):
    self.root = None                             1

  def insert(self, val):                         2
    self.root = self._insert(self.root, val)

  def _insert(self, node, val):
    if node is None:
      return BinaryNode(val)                     3

    if val <= node.value:                        4
      node.left = self._insert(node.left, val)
    else:                                        5
      node.right = self._insert(node.right, val)
    return node                                  6
1

self.root is the root node of the BinaryTree (or None if empty).

2

Use _insert() helper function to insert val into tree rooted at self.root.

3

Base case: to add val to an empty subtree, return a new BinaryNode.

4

If val is smaller than or equal to node’s value, set node.left to be the subtree that results when inserting val into subtree node.left.

5

If val is larger than node value, set node.right to be the subtree that results when inserting val into subtree node.right.

6

This method must return node to uphold its contract that it returns the root of the subtree into which val was inserted.

The insert(val) function in BinaryTree invokes the recursive _insert(node, val) helper function to set self.root to be the subtree that results when inserting val into the subtree rooted at self.root.1

The casual and elegant one-line implementation of insert() is a feature of programs using recursive data structures. The _insert() function both inserts val and returns the root of the resulting subtree.

Tip

While all of the values being inserted are unique in this example, in general, binary search trees can contain duplicate values, which is why the _insert() function checks if val ≤ node.value.

In _insert(node, val), the base case occurs when node is None, which occurs whenever val is requested to be inserted into a nonexistent subtree; it just returns a new subtree rooted by the newly created BinaryNode. For the recursive case, val is inserted into either the left subtree, node.left, or the right subtree, node.right. At the end of the recursive case, it is critical that _insert() returns node to fulfill its obligation of returning the root of the subtree that results from adding val to the subtree rooted at node.

_insert(node, val) maintains the binary search tree property such that all values in the left subtree for node are smaller than or equal to node.value, and values in the right subtree are larger than or equal to node.value.

Try inserting 29 into the binary search tree from Figure 6-3. 29 is larger than the root, so it must be inserted into the right subtree rooted by 53. 29 is smaller than 53, so insert into its left subtree rooted at 26. Finally, 29 is larger than 26, so it forms the new right subtree for 26, as shown in Figure 6-4.

Insert one more value
Figure 6-4. Inserting 29 into the binary search tree example

The order in which values are inserted determines the structure of the final binary tree, as you can see in Figure 6-5. For the binary search tree on the left, you know that 5 was the first value inserted, since it is the root of the tree. In addition, every node must have been inserted after its ancestor.

The binary search tree on the right was formed by inserting the seven values in increasing order, which reveals the worst case for inserting values into a binary search tree; if you rotate the image counterclockwise about 45 degrees, it looks like a linked list, in which case it loses its efficiency. Toward the end of this chapter, I present a strategy to maintain more balanced tree structures in the face of insertions and removals.

Two different structures
Figure 6-5. Different binary search trees when values are inserted in different order

Searching for Values in a Binary Search Tree

The _insert() method recursively finds the appropriate location to insert a new leaf node containing the value to be added. This same recursive approach could simply check whether a value is contained in a binary search tree; in practice, however, the code in Listing 6-5 offers a simpler, non-recursive solution using a while loop.

Listing 6-5. Determining whether a BinaryTree contains a value
class BinaryTree:
  def __contains__(self, target):
    node = self.root                 1
    while node:
      if target == node.value:       2
        return True

      if target < node.value:        3
        node = node.left
      else:
        node = node.right            4

    return False                     5
1

Start the search at the root.

2

If target value is same as node’s value, return True for success.

3

If target is smaller than node’s value, set node to its left subtree to continue search in that subtree.

4

If target had been larger than node’s value, continue search in right subtree.

5

If the search runs out of nodes to inspect, the value does not exist in the tree, so return False.

This __contains()__ function is added to the BinaryTree class.2 Its structure is similar to searching for a value within a linked list; the difference is that the next node to be searched could either be left or right based on the relative value of target.

Removing Values from a Binary Search Tree

Removing a value from a linked list was relatively straightforward—as discussed in Chapter 3—but removing a value from a binary search tree is more challenging. To start with, if the value to be removed is contained in the root node, how do you “stitch together” its orphaned left and right subtrees? Also, there should be a least-effort consistent strategy that works every time. Let’s try to find an intuitive solution to remove the value contained in the root node of a binary search tree. Figure 6-6 offers two possible binary search trees after removing the root value of 19.

Two possible solutions
Figure 6-6. Two possible binary search trees after removing 19 from Figure 6-4

You can confirm that both of these options remain binary search trees: the values in each left subtree remain smaller than or equal to its root, and the values in each right subtree remain larger than or equal to its root. The effort involved appears to be minimal for both options:

  • Option #1: Find and remove the maximum value in the left subtree, and use that value for the root.

  • Option #2: Find and remove the minimum value in the right subtree, and use that value for the root.

Each of these options is acceptable, and I choose to implement the second one. The resulting binary tree is a valid binary search tree because the new root value of 26 is the smallest value in the original right subtree—which means by definition it is smaller than or equal to all values in the revised subtree shaded in Figure 6-6. In addition, it is larger than or equal to all values in the original left subtree because it is larger than or equal to the original root value of 19, which was already larger than or equal to the values in the original left subtree.

Let’s start by solving the sub-problem that removes the minimum value in a given subtree. If you think about it, the minimum value in a subtree cannot have a left child—since otherwise a smaller value would exist. Given the binary search tree in Figure 6-7, the minimum value in the right subtree rooted at 53 is 26, and as you can see, it has no left child. Removing this value only requires “lifting up” its right subtree, rooted at 29, to become the new left subtree to 53. Setting the left child of 53 to be the tree rooted at 29 will always work, since 26 has no left subtree and no values will be lost.

Remove min value
Figure 6-7. Removing minimum value in a subtree

Listing 6-6 contains the helper function in BinaryTree, _remove_min(node), that removes the minimum value in the subtree rooted at node; this function is never called when node is None. When invoking _remove_min() on rc—the right child of the tree in Figure 6-7—the recursive case is invoked, namely to remove the minimum value in the left subtree rooted at 26. This leads to the base case, since 26 has no left subtree, and in its place the function “lifts up” and returns its right subtree rooted at 29 to become the new left subtree to 53.

Listing 6-6. Removing minimum value
def _remove_min(self, node):
  if node.left is None:                    1
    return node.right

  node.left = self._remove_min(node.left)  2
  return node                              3
1

Base case: if node has no left subtree, then it is the smallest value in the subtree rooted at node; to remove it, just “lift up” and return its right subtree (which could be None).

2

Recursive case: remove the minimum value from left subtree, and the returned subtree becomes new left subtree for node.

3

_remove_min() completes the recursive case by returning the node whose left subtree may have been updated.

Once again, this code is brief and elegant. As with the other recursive functions discussed earlier, _remove_min() returns the root node of the modified subtree. With this helper function, I can now complete the implementation of remove() that removes a value from a binary search tree. To visualize what the code must do, Table 6-3 shows an example of the changes to a binary tree when removing the value, 19, contained in its root node.

Table 6-3. Demonstrating how root node is removed from binary search tree
Remove 7

Since the root node contains the value to be removed, set original to be the same as node.
Remove 8

Once the while loop completes, node is changed to refer to the smallest value in the right subtree of original—in this case, the node whose value contains 26. This is going to be the new root for the entire subtree. It is important to see that (a) node has no left subtree, (b) its value is the smallest value in the subtree rooted by 53, and (c) it is larger than or equal to all values in the subtree rooted by 14.
Remove 9

After removing the minimum value from the subtree rooted at original.right (containing value 53), node.right is set to this updated subtree (which consists of the three nodes with values 29, 53, and 58). For a brief moment, original.right and node.right both point to the subtree rooted at 53.
Remove 10

To complete the update, node.left is set to refer to original.left. When _remove() is done, it returns node, which will then “take the place” of original, whether as the root node for the entire binary search tree or as a child node to another node.

The implementation of remove() is shown in Listing 6-7.

Listing 6-7. Removing a value from a BinaryTree
def remove(self, val):
  self.root = self._remove(self.root, val)         1

def _remove(self, node, val):
  if node is None: return None                     2

  if val < node.value:
    node.left = self._remove(node.left, val)       3
  elif val > node.value:
    node.right = self._remove(node.right, val)     4
  else:                                            5
    if node.left is None:  return node.right
    if node.right is None: return node.left        6

    original = node                                7
    node = node.right
    while node.left:                               8
      node = node.left

    node.right = self._remove_min(original.right)  9
    node.left = original.left                      10

  return node
1

Use _remove() helper function to remove val from tree rooted at self.root.

2

Base case: attempting to remove val from nonexistent tree returns None.

3

Recursive case #1: if value to be removed is smaller than node.value, set node.left to be the subtree that results from removing val from node.left.

4

Recursive case #2: if value to be removed is larger than node.value, set node.right to be the subtree that results from removing val from node.right.

5

Recursive case #3: it may be that node is root of subtree and contains value to be removed, so there’s work to be done.

6

Handle easy cases first. If node is a leaf, then None is returned. If it has just one child, then return that child node.

7

Remember original reference to node, since we don’t want to lose track of node’s original left and right subtrees, both of which must exist.

8

Start with node = node.right to find the smallest value in the subtree rooted at node.right: as long as node has a left subtree, then it does not contain the smallest value, so iteratively locate the node with no left subtree—this is the smallest value in the right subtree of original.

9

node will become the new root to the left and right children of original. Here I set node.right to the subtree that results from removing the minimum value from original.right. You might notice that this recursive method essentially repeats the process of the while loop, but this code is much easier to understand than trying to do everything in just one pass.

10

Stitch the subtree rooted at node back together.

The final capability supported by a binary search tree is returning the values in ascending order. In computer science this is known as a traversal.

Traversing a Binary Tree

To process each element in a linked list, start at the first node and use a while loop to follow next references until all nodes are visited. This linear approach can’t work with a binary search tree because there are left and right references to follow. Given the recursive nature of a binary tree data structure, there needs to be a recursive solution. Listing 6-8 contains an elegant recursive solution that uses Python generators.

Listing 6-8. Generator that iterates over values in binary search tree in ascending order
class BinaryTree:

  def __iter__(self):
    for v in self._inorder(self.root):      1
      yield v

  def _inorder(self, node):
    if node is None:                        2
      return

    for v in self._inorder(node.left):      3
      yield v

    yield node.value                        4

    for v in self._inorder(node.right):     5
      yield v
1

Yield all values that result from the in order traversal of binary search tree rooted at self.root

2

Base case: nothing to generate for a nonexistent subtree.

3

To generate all values in order, first generate all values in order from the subtree rooted at node.left.

4

Now it is node’s turn to yield its value.

5

Finally, generate all values in order from the subtree rooted at node.right.

The __iter()__ function repeatedly yields the values provided by the recursive helper function, _inorder(), using a common idiom provided by Python. For the base case of the recursion, when asked to yield the values for a nonexistent binary search tree rooted at node, _inorder() returns and does nothing. For the recursive case, this function relies on the binary search tree property that all values in the subtree rooted at node.left are smaller than or equal to node.value and that all values in the subtree rooted at node.right are larger than or equal to node.value. It recursively yields all values in node.left before yielding its own value, and subsequently yielding the values in node.right. The process is visualized in Figure 6-8 with a binary search tree, T, containing five values.

I have now shown how to search, insert, and remove values from a binary search tree; in addition, you can retrieve these values in ascending order. It’s time to collectively analyze the performance of these fundamental operations.

Iterating values in ascending order
Figure 6-8. Iterating over the values in a binary search tree in ascending order

Analyzing Performance of Binary Search Trees

The determining factor for search, insert, and remove operations is the height of the tree, which is defined as the height of its root node. The height of a node is the number of left or right references you need to get from that node to its most distant descendant leaf node. This means the height of a leaf node is 0.

Tip

The height of a nonexistent binary node cannot be 0, since leaf nodes have a height of 0. The height of None—that is, a nonexistent binary node—is defined as –1 to make computations consistent.

In the worst case, the number of nodes visited during a search is based on the height of the root of the binary search tree. Given N nodes in a binary search tree, what is its height? It depends entirely on the order in which the values had been inserted. A complete binary tree represents the best case since it efficiently stores N = 2k – 1 nodes in a tree whose height is k – 1. The binary tree in Figure 6-9, for example, has N = 63 nodes, and the height of the root node is 5. Searching for a target value will involve no more than 6 comparisons (since with 5 left or right references you will visit 6 nodes). Since 26 – 1 = 63, this means that the time to search for a value is proportional to log (N + 1). But in the worst case, all values were inserted in ascending (or descending) order, and the binary search tree is just a long linear chain, as shown in Figure 6-5. In general, the runtime performance of search is O(h), where h is the height of the binary search tree.

Complete binary tree with 63 nodes
Figure 6-9. Complete binary tree stores the most values with the least height

Inserting a value has the same time complexity as searching for a value—the only difference is that a new leaf node is inserted once the search ends with a nonexistent left or right subtree; so inserting a value is O(h) as well.

Removing a value from a binary search tree requires three steps:

  1. Locate the node containing the value to be removed

  2. Locate the minimum value in the right subtree of the node containing the value to be removed

  3. Remove that value from the right subtree

Each of these substeps in the worst case can be directly proportional to the height.3 At worst, then, the time to remove a value is proportional to 3 × h, where h is the height of the binary search tree. Based on the results from Chapter 2, since 3 is just a multiplicative constant, this means that the time to remove a value remains O(h).

The structure of the binary search tree is based entirely on the order in which the values are inserted and removed. Since the binary search tree cannot control how it is used, it needs a mechanism to detect when its structure is performing poorly. In Chapter 3, I explained how hashtables resized themselves—rehashing all its entries—once a threshold size was hit. It was acceptable for hashtables to do this, because this costly O(N) operation would become ever more infrequently requested using the geometric resizing strategy. As you may recall, doing so enabled the average O(1) runtime performance for get().

The geometric resizing strategy will not work here because there is no simple threshold computation based on N that can determine when to resize, and you can’t ensure that resize events become ever more infrequent: all it takes is a small sequence of awkward insertions to unbalance a tree, as visualized in Figure 6-10. Each node is color-coded by its height.

Inserting values can unbalance a binary tree
Figure 6-10. Unbalanced tree after two insertions

The complete binary tree on the left in Figure 6-10 has a perfectly balanced structure; each leaf node has a height of 0, and the root node has a height of 2. When 29 is inserted—as shown in the middle tree—a new leaf node is created in the proper location. Note that all ancestor nodes of 29 increase their height by 1, and they are shaded accordingly. After 27 is inserted—as shown in the right tree—the tree has lost its balance: its left subtree at 14 has a height of 1, but its right subtree at 53 has a height of 3. Other nodes—such as 26 and 53—are similarly out of balance. In the next section, I explain a strategy for detecting and rebalancing binary search trees.

Self-Balancing Binary Trees

The first known self-balancing binary tree data structure, the AVL tree, was invented in 1962.4 The premise is that as values are inserted into, or removed from, a binary search tree, weaknesses in the structure of the resulting tree are detected and repaired. An AVL tree guarantees that the height difference of any node—defined as the height of the node’s left subtree minus the height of the node’s right subtree—is –1, 0, or 1.

As shown in Listing 6-9, each BinaryNode must store its height in the binary search tree. Whenever a node is inserted into the binary search tree, the height of the affected nodes must be computed so an unbalanced tree node can be detected immediately.

Listing 6-9. Structure of AVL binary node
class BinaryNode:
  def __init__(self, val):
    self.value = val                                        1
    self.left  = None
    self.right = None
    self.height = 0                                         2

  def height_difference(self):                              3
    left_height = self.left.height if self.left else -1     4
    right_height = self.right.height if self.right else -1
    return left_height - right_height                       5

  def compute_height(self):                                 6
    left_height = self.left.height if self.left else -1
    right_height = self.right.height if self.right else -1
    self.height = 1 + max(left_height, right_height)
1

Structure of a BinaryNode is essentially the same as a binary search tree.

2

Record the height for each BinaryNode.

3

Helper function that computes the height difference between left and right subtree.

4

Set left_height to —1 for nonexistent left subtree, or its proper height.

5

Return height difference, which must be left_height subtracting right_height.

6

Helper function that updates the height for a node assuming that the height of its respective left and right subtrees (if they exist) have accurate height values.

Listing 6-10 shows that the node returned by _insert() has its height properly computed.

Listing 6-10. Modify _insert() to compute height properly
  def _insert(self, node, val):
    if node is None:
      return BinaryNode(val)                    1

    if val <= node.value:
      node.left = self._insert(node.left, val)
    else:
      node.right = self._insert(node.right, val)

    node.compute_height()                       2
    return node
1

For the base case, when a newly created leaf node is returned, its height is already 0 by default.

2

When the recursive case completes, val has been inserted into either node.left or node.right. This means the height for node needs to be recomputed.

During the invocation of insert(27), a new leaf node for 27 is added to the binary search tree at the end of a sequence of recursive invocations, depicted in Figure 6-11. The final invocation to _insert() involves the base case where a new leaf node containing 27 is returned. This figure captures the brief moment when both the new leaf node (for 27) and the original leaf node (for 29) have a height of 0. With just one additional statement to compute the node’s height at the end of _insert(), as the recursion unwinds, the height for each ancestor node (highlighted in Figure 6-11) are recomputed—note that these are the only nodes in the binary search tree whose heights need to be adjusted. The compute_height() function captures the logical definition for the height of a node, namely, that it is one greater than the larger of the heights of its children subtrees.

Recursive invocation when inserting a value
Figure 6-11. Recursive invocation when inserting a value

As the recursive invocations unwind, each ancestor node to 27 has its height recomputed. Because each node has an accurate height in the binary search tree, _insert() can detect whenever a node has become unbalanced—that is, when the height of the left and right subtrees for that node differ by more than 1.

Tip

In an AVL tree, the height difference for any node is -1, 0, or 1. The height difference is computed as the height of the node’s left subtree minus the height of the node’s right subtree. If a subtree doesn’t exist, then use -1 for its height.

The node containing 26 leans to the right because its height difference is –1 – 1 = –2; the node containing 53 leans to the left because its height difference is 2 – 0 = 2; lastly the root node leans to the right because its height difference is 1 – 3 = –2. Once these nodes are identified, there needs to be a strategy to adjust the tree in some way to bring it back into balance. In the same way that the height is computed as the recursion unwinds, the _insert() function can immediately detect when the insertion of a new node has unbalanced the tree. It detects the imbalance as the recursion unwinds, which means the first unbalanced node detected is 26.

The designers of the AVL tree invented the concept of a node rotation, which is best described visually in Figure 6-12. The three nodes—containing the values 10, 30, and 50—are shaded to present their height. The root node, containing 50, has height h. The gray triangles are subtrees whose values conform to the binary search tree property. The left subtree of the node containing 10, for example, is labeled 10L, and it contains values that are all smaller than or equal to 10. All you need to know is that the height of this subtree (and the other three shaded subtrees, 10R, 30R, and 50R) is h – 3.

The tree leans to the left: its left subtree has a height of h – 1, while its right subtree has a smaller height of h – 3, meaning the height difference is +2. An AVL tree rebalances itself by detecting this imbalance and rotating nodes to reconfigure the tree, as shown on the right in Figure 6-12. After the rotation, the resulting binary search tree has a height of h – 1, and the node containing 30 has become the new root. This particular rotation is a rotate right, which you can visualize as placing your hand on the original node containing 30 and rotating your hand to the right, which “lifts up” the node containing 30 while “dropping down” the node containing 50.

Rotating a node to the right
Figure 6-12. Rebalancing this binary search tree by rotating the root node to the right

There are four possible unbalanced scenarios in a binary search tree containing just three values, as shown in Figure 6-13. Scenario Left-left represents a simplified version of the example in Figure 6-12, which only needs a rotate right to balance the tree; similarly, scenario Right-right represents its mirror image, needing only a rotate left to bring the tree back into balance. These scenarios are named for the relative positioning of each descendant node to the root. These rotate operations result in a balanced tree whose root node contains 30, with a left child containing 10 and a right child containing 50.

Four necessary rotations
Figure 6-13. Four different node rotations

Scenario Left-right presents a more complicated unbalanced tree that can be rebalanced in two steps. First, rotate left the left subtree rooted at 10, which “drops down” the 10 node and “lifts up” the 30 node, resulting in a tree that matches scenario Left-left. Second, perform a rotate right to balance the tree. This two-step composite operation is called rotate left-right. Scenario Right-left represents the mirror image of scenario Left-right, resulting in a rotate right-left operation that rebalances the tree. The repository contains an optimized implementation for these composite operations.

Two new helper functions resolve situations when a node is unbalanced to the left (or to the right), as shown in Listing 6-11.

Listing 6-11. Helper functions that choose appropriate rotation strategy
  def resolve_left_leaning(node):              1
    if node.height_difference() == 2:
      if node.left.height_difference() >= 0:   2
        node = rotate_right(node)
      else:
        node = rotate_left_right(node)         3
    return node                                7

  def resolve_right_leaning(node):
    if node.height_difference() == -2:         4
      if node.right.height_difference() <= 0:  5
        node = rotate_left(node)
      else:
        node = rotate_right_left(node)         6
    return node                                7
1

A node leans to the left when height difference is +2.

2

Detects the rotate_right case by confirming that node’s left subtree is partially leaning left.

3

Otherwise, node’s left subtree is partially leaning right, meaning a rotate_left_right is in order.

4

A node leans to the right when height difference is –2.

5

Detects the rotate_left case by confirming that node’s right subtree is partially leaning right.

6

Otherwise, node’s right subtree is partially leaning left, meaning a rotate_right_left is in order.

7

Be sure to remember to return node of (potentially rebalanced) subtree.

The strategy is to immediately resolve an unbalanced node once this situation has been detected. The final implementation of _insert() is shown in Listing 6-12, which takes immediate advantage of these resolution helper functions. Adding a value to a left subtree of a node can never make that node right-leaning; similarly, adding a value to a right subtree of a node can never make that node left-leaning.

Listing 6-12. Rotating nodes when an unbalanced node is detected
  def _insert(self, node, val):
    if node is None:
      return BinaryNode(val)

    if val <= node.value:
      node.left = self._insert(node.left, val)
      node = resolve_left_leaning(node)           1
    else:
      node.right = self._insert(node.right, val)
      node = resolve_right_leaning(node)          2

    node.compute_height()
    return node
1

If left subtree is now left-leaning, resolve it.

2

If right subtree is now right-leaning, resolve it.

The implementations for these rotation functions can be found in the code repository. Table 6-4 describes the rotate_left_right case, showing the code and the rebalanced tree. At the top, the new_root and the other affected nodes and subtrees are identified. Below, the tree is rebalanced, and, importantly, new heights are computed for child and node.

Pay attention to how rotate_left_right() returns the new root node for the balanced binary tree, since this unbalanced node could exist within a larger binary tree. There is no need to recompute the height of new_root since the calling function—in _insert() or _remove()—will do that. You can confirm visually that the resulting binary tree still conforms to the binary search tree property: for example, all of the values in 30L are greater than or equal to 10 and less than or equal to 30, so this subtree can be a right subtree of the node containing 10. A similar argument explains why the subtree labeled 30R can be a left subtree to the node containing 50.

Table 6-4. Implementation of rotate left-right
Rotate left-right step 1 
def rotate_left_right(node):
  child = node.left
  new_root = child.right
  grand1  = new_root.left
  grand2  = new_root.right
Rotate left-right step 2 
  child.right = grand1
  node.left = grand2
  new_root.left = child
  new_root.right = node

  child.compute_height()
  node.compute_height()
  return new_root

The revised _insert() method now rebalances the binary search tree as needed. A similar change to _remove() and _remove_min() is straightforward with these helper functions, as shown in Listing 6-13. The code is modified to include four targeted interventions whenever the tree’s structure is changed.

Listing 6-13. Updating _remove() to maintain AVL property
  def _remove_min(self, node):
    if node.left is None: return node.right

    node.left = self._remove_min(node.left)
    node = resolve_right_leaning(node)             1
    node.compute_height()
    return node

  def _remove(self, node, val):
    if node is None: return None

    if val < node.value:
      node.left = self._remove(node.left, val)
      node = resolve_right_leaning(node)           2
    elif val > node.value:
      node.right = self._remove(node.right, val)
      node = resolve_left_leaning(node)            3
    else:
      if node.left is None:  return node.right
      if node.right is None: return node.left

      original = node
      node = node.right
      while node.left:
        node = node.left

      node.right = self._remove_min(original.right)
      node.left = original.left
      node = resolve_left_leaning(node)            4

    node.compute_height()
    return node
1

Removing the minimum value from a subtree rooted at node.left could make node right-leaning; rotate to rebalance as needed.

2

Removing a value from the left subtree of node could make node right-leaning; rotate to rebalance as needed.

3

Removing a value from the right subtree of node could make node left-leaning; rotate to rebalance as needed.

4

After the minimum has been removed from the subtree returned to be node.right, node could be left-leaning; rotate to rebalance as needed.

The AVL implementation now properly rebalances whenever a new value is inserted into the tree or a value is removed. Each rebalancing contains a fixed number of operations and executes in O(1) constant time. Because an AVL tree is still a binary search tree, the search and traversal functions do not need to change.

Using Binary Tree as (key, value) Symbol Table

The same binary search tree structure can be used to implement the symbol table data type introduced in Chapter 3, as shown in Figure 6-14.

BST as symbol table
Figure 6-14. Binary search tree as symbol table: keys are atomic numbers; values are element names

To do this, you have to modify the BinaryNode structure to store both key and value, as shown in Listing 6-14.

Listing 6-14. Updated BinaryNode when using binary tree to store symbol table
class BinaryNode:
  def __init__(self, k, v):
    self.key = k              1
    self.value = v            2
    self.left = None
    self.right = None
    self.height = 0
1

The key is used to navigate the binary search tree.

2

The value contains arbitrary data that is irrelevant to the operation of the binary search tree.

BinaryTree now needs put(k,v) and get(k) functions, instead of insert() and __contains()__, to support the expected interface for a symbol table. The changes are minimal, and only incidental changes are required, so the code is not reproduced here; find it in the associated code repository. When navigating through the binary search tree, that is, whether to go left or right, the decision is based on node.key.

Using a binary search tree provides the added benefit that the keys can be retrieved from the symbol table in ascending order using the __iter()__ traversal function.

Chapter 3 described how open addressing and separate chaining can implement the symbol table data type. It’s worth comparing the runtime performance of a binary search tree against the results of open addressing and separate chaining hashtables, as shown in Table 3-4. This trial inserts N = 321,129 words from the English dictionary into a symbol table. What is the smallest height for a binary tree that stores all of these words? Recall that this height is computed by the formula log(N + 1) – 1, which is 17.293. After inserting all of these words in ascending order from the English dictionary, the height of the resulting AVL binary search tree is 18, which further demonstrates the efficiency of AVL trees in storing information.

The hashtable implementations from Chapter 3 significantly outperform binary search trees, as shown in Table 6-5. If you ever need the keys for a symbol table in ascending order, then I recommend retrieving the keys from the symbol table and then sorting them separately.

Table 6-5. Comparing AVL symbol table implementation with hashtables from Chapter 3 (time in seconds)
Type Open addressing Separate chaining AVL trees

Build time

0.54

0.38

5.00

Access time

0.13

0.13

0.58

Using the Binary Tree as a Priority Queue

Given that the heap data structure described in Chapter 4 is based on a binary tree structure, it is only natural to compare the runtime performance of a priority queue implemented using an AVL binary search tree where the priority is used to navigate the structure of the binary search tree, as shown in Figure 6-15.

BST as priority queue
Figure 6-15. Binary search tree as priority queue: priorities are atomic numbers; values are element symbols

There are two benefits to using a binary search tree to implement a priority queue:

  • An array-based heap must create storage for a fixed number of values in advance. Using a binary search tree, the structure can grow to be as large as needed.

  • In the heap structure, there is no way to provide an iterator of the entries in the priority queue in priority order without dequeuing the values.5 With a binary search tree structure, this capability now exists using the traversal logic.

To get started, BinaryNode now stores both value and priority, as shown in Listing 6-15. The priority field will be used to navigate the binary tree for the search, insert, and remove operations.

Listing 6-15. Updated BinaryNode when using binary tree to store priority queue
class BinaryNode:
  def __init__(self, v, p):
    self.value = v            1
    self.priority = p         2
    self.left  = None
    self.right = None
    self.height = 0
1

The value contains arbitrary data that is irrelevant to the operation of the binary search tree.

2

The priority is used to navigate the binary search tree.

In  a  max  binary  heap,  the  entry  with  highest  priority  is  in  storage[1],  and  it  can  be  located  in  O(1)  constant  time.  This  is  not  the  case  when  using  a  binary  search  tree  to  store  a  priority  queue.  The  BinaryNode  with  highest  priority  is  the  rightmost  node  in  the  binary  tree.  To  locate  this  value  requires  O(log N)  runtime  performance,  if  the  underlying  binary  tree  is  balanced  using  the  techniques  described  in  this  chapter.

The biggest change, however, is that when a priority queue uses a binary search tree for storage, the only value to remove is the one with highest priority; this means the general purpose remove() function is not needed. In its place, a _remove_max() helper function is added to PQ, as shown in Listing 6-16. The other helper functions are part of the standard priority queue interface. Note that the count, N, of pairs is stored and managed by the PQ class.

Listing 6-16. PQ class provides enqueue() and dequeue() functions
class PQ:
  def __init__(self):
    self.tree = BinaryTree()                                  1
    self.N = 0

  def __len__(self):
    return self.N

  def is_empty(self):
    return self.N == 0

  def is_full(self):
    return False

  def enqueue(self, v, p):
    self.tree.insert(v, p)                                    2
    self.N += 1

  def _remove_max(self, node):                                3
    if node.right is None:
      return (node.value, node.left)                          4

    (value, node.right) = self._remove_max(node.right)        5
    node = resolve_left_leaning(node)                         6
    node.compute_height()                                     7
    return (value, node)

  def dequeue(self):                                          8
    (value, self.tree.root) = self._remove_max(self.tree.root)
    self.N -= 1
    return value                                              9
1

Use a balanced binary search tree for storage.

2

To enqueue a (v, p) pair, insert that pair into the binary search tree and increment N count.

3

The _remove_max() helper method both removes the node with maximum priority from the subtree rooted at node and returns its value and the node of the resulting subtree as a tuple.

4

Base case: with no right subtree, this node has maximum priority; return both the value in the node being deleted and the left subtree that will eventually take its place.

5

Recursive case: retrieve removed value and root of updated subtree.

6

If node is out of balance (it could now lean left), fix with rotations.

7

Compute node height before returning it along with value that was removed.

8

The dequeue() method removes node with maximum priority from the binary search tree and returns its value.

9

After decrementing count, N, return the value that had been associated with highest priority.

The runtime performance of this priority queue implementation still offers O(log N) behavior, although in absolute terms it is twice as slow as the heap-based priority queue implementation from Chapter 4. The reason is that maintaining the AVL binary search tree structure is more work than actually needed for a priority queue. Still, if you need the ability to iterate over its (value, priority) pairs in the order in which they would be removed, this is an efficient alternative.

Summary

Binary trees are a dynamic, recursive data structure that organizes its values into left and right substructures, offering the potential to evenly subdivide a collection of N values into two structures, each containing (more or less) N/2 values. Binary trees form the basis for countless other recursive data structures that lead to efficient implementations, including:

  • Red-black trees, which offer a more efficient approach for balancing binary search trees, although the implementation is more complicated than with AVL trees.

  • B-trees and B+ trees, used for databases and file systems.

  • R-trees and R∗ trees, used for spatial information processing.

  • k-d trees, Quadtrees, and Octrees for space-partitioning structures.

To summarize:

Challenge Exercises

  1. Write a recursive count(n, target) function that returns the number of times that target exists within the linked list whose first node is n.

  2. Sketch the structure of a binary search tree with N nodes that requires O(N) time to find the two largest values. Next, sketch the structure of a binary search tree with N nodes that requires O(1) time to find the two largest values.

  3. What if you wanted to find the kth smallest key in a binary search tree? An inefficient approach would be to traverse the entire tree until k nodes have been visited. Instead, add a function, select(k), to BinaryTree that returns the kth smallest key for k from 0 to N – 1. For an efficient implementation, you will need to augment the BinaryNode class to store an additional field, N, that records the number of nodes in the subtree rooted at that node (including that node itself). A leaf has an N value of 1, for example.

    Also add the companion method, rank(key), to BinaryTree that returns an integer from 0 to N – 1 that reflects the rank of key in sorted order (or in other words, the number of keys in the tree strictly less-than key).

  4. Given the values [3,14,15,19,26,53,58], there are 7! = 5,040 ways to insert these seven values into an empty binary search tree. Compute the number of different ways that the resulting tree is perfectly balanced, with a height of 2, such as the binary search tree shown in Figure 6-3.

    Can you generalize your result to an arbitrary collection of 2k-1 values and present a recursive formula c(k) that computes this for any k?

  5. Write a contains(val) method for BinaryTree that invokes a recursive contains(val) method in BinaryNode.

  6. As described in this chapter, AVL trees are self-balancing. For a given N, can you compute the maximum height of an AVL tree containing N values, since they cannot all be so perfectly compact as a complete binary tree? Generate 10,000 random AVL trees of size N, and record the maximum observed height for each N.

    Create a table that records whenever this maximum observed height increases. Predict the values of N such that an AVL tree of N nodes can have a tree height that is one greater than any AVL tree with N – 1 nodes.

  7. Complete the SpeakingBinaryTree in Listing 6-17 whose insert(val) operation produces English descriptions of the actions as they are performed. Table 6-2 contains the desired output for each of the corresponding operations. This recursive operation is different from others in this chapter because it processes “top-down,” whereas most recursive functions process “bottom-up” from base cases.

    Listing 6-17. Enhance the _insert() method to return description of what happened
    class BinaryNode:
  def __init__(self, val):
    self.value = val
    self.left  = None
    self.right = None

class SpeakingBinaryTree:
  def __init__(self):
    self.root = None

  def insert(self, val):
    (self.root,explanation) = self._insert(self.root, val,
         'To insert `{}`, '.format(val))
    return explanation

  def _insert(self, node, val, sofar):
    """
    Return (node,explanation) resulting from inserting val into subtree
    rooted at node.
    """

    Modify the _insert() function to return a tuple (node, explanation), where node is the resulting node and explanation contains the growing explanation for the actions.

  8. Write a method check_avl_property(n) that validates the subtree rooted at n to ensure that (a) that each descendant node’s computed height is correct, and (b) that each descendant node satisfies the AVL tree property.

  9. Write a tree_structure(n) function that produces a string with parentheses in prefix order to capture the structure of the binary tree rooted at n. In prefix order, the value for the node is printed first, before the left representation and right representation. This string should use commas and parentheses to separate information, so it can be parsed later. For the complete binary tree in Figure 6-3, the resulting string should be '(19,(14,(3,,),(15,,)),(53,(26,,),(58,,)))', while for the binary tree in the left side of Figure 6-5, the resulting string should be '(5,(4,(2,(1,,),(3,,)),),(6,,(7,,)))'.

    Write the companion recreate_tree(expr) function that takes in an expr tree structure string using parentheses and returns the root node of a binary tree.

  10. If you count rotate left-right and rotate right-left as single rotations (in addition to rotate left and rotate right), then you will never need more than a single rotation when inserting a value into an AVL binary search tree. However, when removing a value from an AVL tree, you might need multiple rotations.

    What is the smallest AVL binary search tree that requires multiple node rotations when a single value is removed? Such a tree would have to have at least four nodes. To answer this question, you will have to instrument the rotation methods to increase a count for the number of times a rotation is used. Also, use the results of tree_structure() in the previous exercise to record the tree so you can recover its structure after you have detected the multiple rotations. Write a function that (a) generates 10,000 random AVL trees containing between 4 and 40 nodes, and (b) for each of these trees, select one of its random values to remove. You should be able to compute the size of the AVL trees that require up to three rotations for a remove request. As a hint, you should be able to generate an AVL tree with 4 nodes that requires 1 rotation for a given remove request, and an AVL tree with 12 nodes that requires 2 rotations for a given remove request. What is the smallest AVL tree that you can find which requires 3 rotations for a given remove request?

  11. A complete binary tree with N = 2k – 1 nodes is the most compact representation for storing N nodes. This question asks what is the “least compact” AVL tree you can construct. A Fibonacci tree is an AVL tree such that in every node, the height of its left subtree is bigger (by just 1) than the height of its right subtree. Think of this as an AVL tree that is one insert away from rebalancing. Write a recursive function, fibonacci_avl(N), for N > 0 that returns a BinaryNode representing the root of a Fibonacci tree. It is simpler to do this without involving any BinaryTree objects. The root node returned contains the value FN. For example, fibonacci_avl(6) would return the root node for the binary tree depicted in Figure 6-16.

    Fibonacci AVL Tree
    Figure 6-16. A Fibonacci tree with twelve nodes

1 All recursive helper functions start with an underscore (_) to declare that these functions are not intended to be part of the public interface for BinaryTree.

2 Implementing this function means a program can use the Python in operator to determine if a value is contained in a BinaryTree object.

3 See a challenge exercise at the end of the chapter on this point.

4 Named after the inventors Adelson-Velsky and Landis.

5 See challenge exercise at end of this chapter showing how to do this.