© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
M. IndenPython Challengeshttps://doi.org/10.1007/978-1-4842-7398-2_8

8. Binary Trees

Michael Inden1  
(1)
Zurich, Switzerland
 

While Python provides list, sets, and dictionaries as a rich variety of real-world data structures, it unfortunately does not include trees for direct use. However, they are helpful for various use cases and therefore desirable. Because the topic of trees is quite extensive and not to go beyond the scope of this book, I will deal mainly with binary trees and binary search trees as special cases.

Before you look at trees in more detail, I would like to mention some fields of usage:

  • A file system is hierarchically structured and can be modeled as a tree. Here the nodes correspond to the directories and the leaves to the files.

  • Mathematical calculations can be represented by trees. You will explore this in an exercise later.

  • In the area of databases, B-trees1 are used for efficient storage and search.

  • In compiler construction, you can use an abstract syntax tree (AST) to represent the source code.2

8.1 Introduction

In this introduction, you’ll first learn some terminology before briefly exploring binary tree and binary search trees. After that, I’ll discuss traversal and some properties of trees. Finally, I’ll introduce three trees that are used repeatedly in the text and the assignments.

8.1.1 Structure, Terminology, and Examples of Use

Trees allow both structured storage and efficient access to data managed there. For this purpose, trees are strictly hierarchical and, as in real trees, no branch grows back into the trunk. A branching point is called node and stores a value. A node at the end of a branch is called leaf —values are also found there. The connecting branch pieces are called edges . Figure 8-1 gives a first impression.
Figure 8-1

A tree with some nodes and leaves

The figure illustrates that trees consist of hierarchically organized nodes. They start from a root (which, interestingly enough, is located at the top in computer science), branch out into several children, which in turn can have any number of child nodes. Thus, they are parents and represent the roots of subtrees. Each node is referenced by exactly one other node.

8.1.2 Binary Trees

A binary tree is a special tree in which each node stores one value, and each node possesses at most two successors, often called left and right. This restriction makes it easier to express many algorithms. As a result, the binary tree is widely used in computer science. It also forms the basis for the binary search tree presented in the following.

Binary tree, homemade A binary tree can be realized with little effort by the following class called BinaryTreeNode :
class BinaryTreeNode:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.item = item
    def is_leaf(self):
        return self.left is None and self.right is None
    def __str__(self):
        return "BinaryTreeNode [item=%s, left=%s, right=%s]" %
                (self.item, self.left, self.right)

For the examples in this book, you do not need to model the binary tree as a standalone class called BinaryTree, but you will always use a special node as a root of the above type BinaryTreeNode. However, to further simplify the handling in your own and especially more complex business applications, the definition of a class BinaryTree is a good idea. There you can also provide various useful functionalities.

8.1.3 Binary Trees with Order: Binary Search Trees

Sometimes the terms “binary tree” and “binary search tree” (BST for short) are used interchangeably, but this is not correct. A binary search tree is indeed a binary tree, but one with the additional property that the nodes are arranged according to their values. The constraint is that the root’s value is greater than that of the left successor and less than that of the right successor. This constraint applies recursively to all subtrees, as illustrated by Figure 8-2. Consequently, a BST does not contain any value more than once.
Figure 8-2

Example of a binary search tree with letters

Search in a BST A search in a BST can be performed in logarithmic time due to the ordering of the values. You implement the function find(startNode, searchFor) for this purpose. Depending on the comparison of the value with the current node’s value, the search continues in the appropriate part of the tree until the value is found. If it is not found, None is returned.
def find(current_node, search_for):
    # recursive termination
    if current_node is None:
        return None
    # recursive descent to the left or right depending on the comparison
    if current_node.item < search_for:
        return find(current_node.right, search_for)
    if current_node.item > search_for:
        return find(current_node.left, search_for)
    return current_node
Insertion into a BST The insertion into a BST may be expressed recursively as well. The insertion has to start at the root so that the ordering of values within the BST can be ensured.
def insert(current_node, value):
    # recursive termination
    if current_node is None:
        return BinaryTreeNode(value)
    # recursive descent: to the left or right depending on the comparison
    if value < current_node.item:
        current_node.left = insert(current_node.left, value)
    elif value > current_node.item:
        current_node.right = insert(current_node.right, value)
    return current_node
Example of a BST The functions shown earlier are also part of the utility module for this chapter called tree_utils. With it, BSTs can be constructed quite easily and readably. In the following, you use the trick underscore as a prefix to keep the names of the nodes as speaking as possible. Besides, you only need the assignment to a variable if you want to continue working with the node. In particular, however, the root is always returned.
_3 = BinaryTreeNode(3)
insert(_3, 1)
insert(_3, 2)
insert(_3, 4)
TreeUtils.nice_print(_3)
print("tree contains 2?", find(_3, 2))
print("tree contains 13?", find(_3, 13))
This generates the following output:
               3
         |-----+-----|
         1           4
         +--|
            2
tree contains 2? BinaryTreeNode [item=2, left=None, right=None]
tree contains 13? None
Problematic insertion order Please note that the sequence in which elements are added can greatly impact the performance of subsequent actions such as searches. I cover this briefly in Section 8.1.5. The following example demonstrates how quickly a tree degenerates into something like a list:
_4 = BinaryTreeNode(4)
insert(_4, 3)
insert(_4, 2)
insert(_4, 1)
TreeUtils.nice_print(_4)
This generates the following output:
                         4
             |-----------+
             3
       |-----+
       2
    |--+
    1
HINT: ASCII OUTPUT OF TREES

For the output of trees in the examples and exercises I call function nice_print(). Its implementation is developed in Exercise 13.

8.1.4 Traversals

When traversing a tree, a distinction is made between depth-first and breadth-first searches. Figure 8-3 illustrates both.
Figure 8-3

Procedure for a depth-first search and a breadth-first search

In a depth-first search, you traverse the tree as deeply as possible. With the breadth-first search, you move from the root node level by level through the tree. This is why it is also called level order or breadth-first.

Breadth-First/Level Order

The following sequence results for the tree from the example when traversing the levels from the root node downwards—the implementation is the subject of Exercise 5.
a b c d e f g h i j k

Conversion from tree to list A great advantage of the level order traversal is its good traceability and comprehensibility. If you have a tree in mind, you can easily predict this traversal and its result. This is an important and useful feature, especially when testing.

Let’s assume that you have already solved Exercise 5 and thus have access to the implementation. Based on it, you can convert a tree into a list as follows:
def convert_to_list(node):
    result = []
    levelorder(node, lambda item: result.append(item))
    return result

Depth-First Searches

The three known depth-first search methods are preorder, inorder, and postorder. Preorder first processes the node itself and then those from the left and then the right subtree. For inorder, the processing order is first the left subtree, then the node itself, and then the right subtree. Postorder processes first the subtrees on the left, then on the right, and finally the node itself. The three depth-first search methods iterate through the previously shown values as follows:
Preorder:   a b d h e i j c f k g
Inorder:    h d b i e j a f k c g
Postorder:  h d i j e b k f g c a
The outputs are not quite as intuitive. In the case of a BST, the inorder traversal returns the nodes’ values according to the order of their values. This yields 1 2 3 4 5 6 7 for the following tree:
            4
      |-----+----|
      2          6
   |--+--|    |--+--|
   1     3    5     7
Interestingly, these traversals can be easily implemented recursively. The action is highlighted in bold in each case:
def preorder(node):
    if node is None:
        return
    print(node.item)
    preorder(node.left)
    preorder(node.right)
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.item)
    inorder(node.right)
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.item)
NOTE: PRACTICAL RELEVANCE OF POSTORDER
Postorder is an important type of tree traversal for the following use cases:

  • Delete: When deleting a root node of a subtree, you must always ensure that the child nodes are also deleted correctly. A postorder traversal is a good way to do this.

  • Calculations of sizes: To determine the size of a directory or a hierarchical project’s duration, postorder is best suited.

8.1.5 Balanced Trees and Other Properties

One speaks of balanced trees if in a binary tree the heights of the two subtrees differ by at most 1 (sometimes by some other constant value). The opposite is a degenerated tree, which arises from, among other things, inserting data in ways that are awkward for the tree, specifically when numbers are added in an ordered fashion into a binary search tree. This causes the tree to degenerate into a linear list, as you saw in an example in section 8.1.3.

Sometimes one or more rotation(s) restores the balance. For the tree from the introduction, a rotation to the left and one to the right is visualized in Figure 8-4. In the middle, you can see the balanced starting position.
Figure 8-4

Rotation to the left, original, rotation to the right

The Properties Level and Height

As indicated in the introduction, trees are hierarchically structured and consist of nodes, which optionally have child nodes and may be nested arbitrarily deep. To describe this, the two terms level and height exist. The level is usually counted from 0 and starts at the root and then goes down to the lowest leaf. For height, the following applies. For a single node, it is 1. It is determined by the number of nodes on the way down to the lowest leaf for a subtree. This is visualized in Figure 8-5 where some nodes labeled as a child are, in fact, also the parent of others.
Figure 8-5

Level and height of a tree

The Properties Completeness and Perfectness

A complete binary tree is characterized by the fact that all levels must be completely filled, except for the last level. Moreover, all nodes have to be as far to the left as possible in the last level, so there are no gaps or all nodes are present.

In a complete binary tree , values may be missing on the right side (in algorithmics this is also called left-full):
     4
    /
  2    6
 /   /
1  3 5
If all positions are occupied, this is called a perfect tree.
     4
    /
   2   6
  /   /
 1   3 5  7
The following constellation (here the missing 5 from the upper tree) is not allowed in a binary tree in the context of completeness (because the tree is then not left-full):
     4
    /
   2   6
  /    
 1   3   7
Let’s try something more formal:

  • A perfect binary tree is one in which all leaves are on the same level and all nodes have two successors each.

  • A complete binary tree is one in which all levels are completely filled—except for the last one, where nodes may be missing, but only as far to the right as possible.

  • A full binary tree means that each node has either no children or two children, as shown in the following diagram:

      4
     / 
    2   6
       / 
      5   7

This is the weakest requirement.

A graphical illustration for these definitions can be found online at www.programiz.com/dsa/complete-binary-tree.

8.1.6 Trees for the Examples and Exercises

Because you will repeatedly refer to some typical tree structures in the following, you implement three creation functions in the utility module example_trees.

Tree with Letters and Numbers

To try out tree traversal and other actions, construct a tree of seven nodes. Therefore you define objects of type BinaryTreeNode, which still have to be connected appropriately after their creation. For simplicity, the examples here are implemented without information hiding. Consequently, you directly access the attributes left and right.
def create_example_tree():
    a1 = BinaryTreeNode("a1")
    b2 = BinaryTreeNode("b2")
    c3 = BinaryTreeNode("c3")
    d4 = BinaryTreeNode("d4")
    e5 = BinaryTreeNode("e5")
    f6 = BinaryTreeNode("f6")
    g7 = BinaryTreeNode("g7")
    d4.left = b2
    d4.right = f6
    b2.left = a1
    b2.right = c3
    f6.left = e5
    f6.right = g7
    return d4
This results in the following tree with root d4:
           d4
     |-----+-----|
    b2          f6
 |--+--|      |--+--|
a1    c3     e5    g7

You may be surprised about the combination of letters and numbers. I chose this intentionally because it allows understanding some algorithms a bit easier—for example, to check traversals’ order.

Trees with Textual and Real Digits

For some exercises, you also need a tree where the nodes’ values consist only of digits (but textually as string). Because it is impossible to name the variables for the individual nodes with digits, let’s use the trick of starting the variable name with an underscore.

To construct the tree, utilize the function insert(), which puts the value to be inserted in the appropriate place for it—this is only possible if you work with a BST and its order. As you can easily see, this will be much easier than the manual linking shown before.
def create_number_tree():
    _4 = BinaryTreeNode("4")
    insert(_4, "2")
    insert(_4, "1")
    insert(_4, "3")
    insert(_4, "6")
    insert(_4, "5")
    insert(_4, "7")
   return _4
This results in the following tree:
         4
   |-----+-----|
   2           6
|--+--|     |--+--|
1     3     5     7
Variant with integers The tree shown is generated as a variant for integers as follows:
def create_integer_number_tree():
    _4 = BinaryTreeNode(4)
    insert(_4, 2)
    insert(_4, 1)
    insert(_4, 3)
    insert(_4, 6)
    insert(_4, 5)
    insert(_4, 7)
    return _4

8.2 Exercises

8.2.1 Exercise 1: Tree Traversal (★★✩✩✩)

Extend the functions presented in the introduction for the traversing trees so that they can perform any action on the current node during the traversal. To do this, add an action to the respective signature, such as for inorder: inorder(node, action).

Bonus: Fill up a Tree into a List Build a representation of the values of the nodes in the form of a list. To do this, write function to_list(node) that returns the values based on an inorder traversal, and functions to_list_preorder(node) and to_list_postorder(node) that are based on a preorder and postorder traversal, respectively.

Example

When using the following tree
            d4
       |-----+-----|
      b2          f6
   |--+--|     |--+--|
  a1    c3    e5    g7
the conversions should result in something similar to
to_list: ['a1', 'b2', 'c3', 'd4', 'e5', 'f6', 'g7']
to_list_preorder: ['d4', 'b2', 'a1', 'c3', 'f6', 'e5', 'g7']
to_list_postorder: ['a1', 'c3', 'b2', 'e5', 'g7', 'f6', 'd4']

8.2.2 Exercise 2: Inorder, Preorder, and Postorder Iterative (★★★★✩)

In the introduction, you learned about inorder, preorder, and postorder as recursive variants. Now implement these types of traversals iteratively.

Example

Again, you use the following tree:
          d4
     |-----+-----|
    b2          f6
 |--+--|     |--+--|
a1    c3    e5    g7
The three depth-first search methods traverse this tree as follows:
Preorder:   d4 b2 a1 c3 f6 e5 g7
Inorder:    a1 b2 c3 d4 e5 f6 g7
Postorder:  a1 c3 b2 e5 g7 f6 d4

8.2.3 Exercise 3: Tree Height (★★✩✩✩)

Implement function get_height(node) to determine the height for a tree and for subtrees with a single node as root.

Example

The following tree of height 4 is used as a starting point:
                      E
          |-----------+-----------|
          C                       G
    |-----|                 |-----+-----|
    A                       F           H
                                        |--|
                                           I

8.2.4 Exercise 4: Lowest Common Ancestor (★★★✩✩)

Compute the lowest common ancestor (LCA) for two nodes, A and B, hosted in an arbitrary binary search tree. The LCA denotes the node that is the ancestor of both A and B and is located as deep as possible in the tree—the root is always the ancestor of both A and B. Write function find_lca(start_node, value1, value2), which, in addition to the start node of the search (usually the root), also receives lower and upper limits, which indirectly describe the nodes that are closest to these values. If the values for the limits are outside the range of values, then there is no LCA and it returns None.

Example

The following binary tree is shown. If the lowest common ancestor is determined for the nodes with the values 1 and 5, this is the node with the value 4. In the tree, the respective nodes are circled and the ancestor is additionally marked in bold.
                        6
            |-----------+-----------|
            ➃                      7
      |-----+-----|
      2           ➄
   |--+--|
   ➀    3

8.2.5 Exercise 5: Breadth-First (★★★✩✩)

In this exercise, you are asked to implement the breadth-first search, also called level order, using the function levelorder(start_node, action). The breadth-first search starts at the given node—usually the root—and then works its way through the tree level by level.

Note

Use a queue to store data on the nodes yet to be visited. The iterative variant is a bit easier to implement than the recursive one.

Examples

For the following two trees, the sequence 1 2 3 4 5 6 7 (for the left) and M I C H A E L (for the right) are to be determined as the result.
          1                      M
    |-----+-----|          |-----+-----|
    2           3          I           C
 |--+--|     |--+--|    |--+--|    |---+--|
 4     5     6     7    H     A    E      L

8.2.6 Exercise 6: Level Sum (★★★★✩)

In the previous exercise, you implemented the breadth-first search. Now you want to sum up the values per level of a tree. For this purpose, let’s assume that the values are natural numbers of type int. Write function level_sum(start_node).

Example

For the tree shown, the sums of the values of the nodes per level should be calculated and return the following result: {0=4, 1=8, 2=17, 3=16}.
                    4
        |-----------+-----------|
        2                       6
  |-----+-----|           |-----+-----|
  1           3           5           8
                                   |--+--|
                                   7     9

Level

Value(s)

Result

0

4

4

1

2, 6

8

2

1, 3, 5, 8

17

3

7, 9

16

8.2.7 Exercise 7: Tree Rotate (★★★✩✩)

Binary trees, especially binary search trees, may degenerate into lists if values are inserted only in ascending or descending order. An unbalance can be addressed by rotating parts of the tree. Write the functions rotate_left(node) and rotate_right(node) that rotate the tree around the node passed as parameter to the left or right, respectively.

Example

Figure 8-6 visualizes a rotation to the left and a rotation to the right with the balanced starting position in the middle.
Figure 8-6

Rotation to the left, original, rotation to the right

8.2.8 Exercise 8: Reconstruction (★★★✩✩)

Exercise 8a: Reconstruction from a List (★★✩✩✩)

In this exercise, you want to reconstruct a binary search tree that is as balanced as possible from an ascending sorted list of natural numbers.

Example

For example, let these values be given:
egin{lstlisting}
values = [1, 2, 3, 4, 5, 6, 7]
Then the following tree should be reconstructed from them:
           4
     |-----+-----|
     2           6
  |--+--|     |--+--|
  1     3     5     7

Exercise 8b: Reconstruction from Inorder/Preorder (★★★✩✩)

Suppose the sequence of values in preorder and inorder is given, each prepared as a list. This information about an arbitrary binary tree should be used to reconstruct the corresponding tree. Write function reconstruct(preorder_values, inorder_values).

Example

Two sequences of values of the traversals are as follows. Based on these values, you should reconstruct the tree shown in the previous part of the exercise.
preorder_values = [4, 2, 1, 3, 6, 5, 7]
inorder_values = [1, 2, 3, 4, 5, 6, 7]

8.2.9 Exercise 9: Math Evaluation (★★✩✩✩)

Consider using a tree to model mathematical expressions with the four operators +, −, /, and ∗. It is your task to compute the value of individual nodes, including in particular the value of the root node. For this purpose, write function evaluate(node).

Example

Represent the expression 3 + 7 ∗ (7 − 1) by the following tree to compute the value 45 for the root node:
               +
   |-----------+-----------|
   3                       *
                     |-----+-----|
                     7           -
                              |--+--|
                              7     1

8.2.10 Exercise 10: Symmetry (★★✩✩✩)

Check if an arbitrary binary tree is symmetric in its structure. Therefore, write function is_symmetric(node). In addition to the structural examination, you can also check for equality of values.

Examples

To check for symmetry, you use a binary tree that is symmetric in structure (left) and a binary tree that is also symmetric concerning values (right).
           4                       1
     |-----+-----|                /
     2           6               2   2
  |--+--|     |--+--|           /    
  1     3     5     7           3     3
NOTE: THE SYMMETRY PROPERTY
In a symmetric binary tree, the left and right subtree are mirrored through the root along an imaginary vertical line (indicated by |):
      1
    / |
   2  |  2
  /   |   
 3    |    3

Depending on the definition, a comparison of the values can be omitted for the symmetry. In this case, only the structural organization can be counted as relevant.

Bonus: Mirror tree In the hint box, I indicated a mirror axis through the root. Create function invert(node) that mirrors the nodes of a tree at this implied line through the root.

Example

A mirroring looks like this:
         4                            4
   |-----+-----|                |-----+-----|
   2           6      =>        6           2
|--+--|     |--+--|          |--+--|     |--+--|
1     3     5     7          7     5     3     1

8.2.11 Exercise 11: Check Binary Search Tree (★★✩✩✩)

In this exercise, you are to check whether an arbitrary binary tree fulfills the property of a binary search tree (BST), so if the values in the left subtree are smaller than the root node’s value and those in the right subtree are larger—and this holds for each subtree starting from the root. For simplification, assume int values. Write function is_bst(node).

Example

Use the following binary tree, which is also a binary search tree. For example, if you replace the number 1 with a larger number on the left side, it is no longer a binary search tree. However, the right subtree under the 6 is still a binary search tree.
         4
   |-----+-----|
   2           6
|--+--|     |--+--|
1     3     5     7

8.2.12 Exercise 12: Completeness (★★★★★)

Check the completeness of a tree. To do this, you initially solve the basics in the first two parts of the exercise and then proceed to the trickier completeness check.

Exercise 12a: Number of Nodes (★✩✩✩✩)

Count how many nodes are contained in any binary tree. To do this, write function count_nodes(node).

Example

For the binary tree shown, the value 7 should be determined. If you remove the right subtree, the tree consists of only 4 nodes.
          4
    |-----+-----|
    2           6
 |--+--|     |--+--|
 1     3     5     7

Exercise 12b: Check for Full/Perfect (★★✩✩✩)

For an arbitrary binary tree, check if all nodes have two successors or leaves each, and thus the tree is full. For perfection, all leaves must be at the same height. Write functions is_full(node) and is_perfect(node).

Example

The binary tree shown is both perfect and full. If you remove the two leaves below the 2, it is no longer perfect but still full.
Full and perfect           Full but not perfect
          4                        4
    |-----+-----|            |-----+-----|
    2           6            2           6
 |--+--|     |--+--|                  |--+--|
 1     3     5     7                  5     7

Exercise 12c: Completeness (★★★★✩)

In this subtask, you are asked to check if a tree is complete as defined in the introduction, so a binary tree with all levels fully filled, with the allowed exception on the last level where nodes may be missing, but only with gaps as far to the right as possible.

Example

In addition to the perfect tree used so far, the following tree is also complete by definition. However, if you remove the children from node H, the tree is no longer complete.
                      F
          |-----------+-----------|
          D                      H
    |-----+-----|          |-----+-----|
    B           E          G           I
 |--+--|
 A     C

Exercise 12d: Completeness Recursive (★★★★★)

In this last subtask, the following challenge remains to be mastered as a special treat. The check is to be solved without additional data structures and purely recursively. At first, this sounds hardly feasible, so I’ll give a hint.

Tip

Develop the solution step by step. Create an auxiliary data structure that models whether or not a node exists for a certain position. Then traverse the tree and mark the positions appropriately. Afterwards, convert this implementation to a purely recursive one without the auxiliary data structure.

Example

As before, the following tree is complete by definition:
                       F
           |-----------+-----------|
           D                       H
     |-----+-----|           |-----+-----|
     B           E           G           I
  |--+--|
  A     C

8.2.13 Exercise 13: Tree Printer (★★★★★)

In this exercise, you are to implement a binary tree’s graphical output, as you have seen before in the examples. Therefore, you initially solve the basics in the first three parts of the assignment and then proceed to the trickier graphical presentation of trees.

Tip

Use a fixed grid of blocks of width three. This significantly contributes to a balanced representation and reduces complexity.

Example

The following tree should cover various special cases:
                      F
          |-----------+-----------|
          D                       H
    |-----+                       +-----|
    B                                   I
 |--+--|
 A     C

Exercise 13a: Width of a Subtree (★★✩✩✩)

In this part of the exercise, you are asked to find the maximum width of a subtree of a given height using the function subtree_width(height). For simplicity, you assume that a maximum of three characters represents the nodes. Besides, there is a distance of at least three characters between them. This is true for the leaves when the tree is full. On higher levels, there is naturally more space between the nodes of two subtrees.

Examples

On the left in Figure 8-7, you see a tree of height 2, and on the right, a tree of height 3. Based on the grid of 3, you get 9 and 21 as widths.

Height

Total width

Width of subtree

1

3

0 (no subtree existing)

2

9

3

3

21

9

4

45

21

Figure 8-7

Tree width

Exercise 13b: Draw Node (★★✩✩✩)

Write function draw_node(current_node, line_length) that creates a graphical output of a node, generating the given set of spaces appropriately. The node value should have a maximum of three characters and be placed in the middle.

Tip

Remember that if the current node has a left successor, the representation of the layer below starts on the left with the string ‘ |-’.

Example

The example in Figure 8-8 shows a single node with a spacing of five characters. Besides, the node value is center-aligned in a three-character box.
Figure 8-8

Dimensions when drawing nodes

Exercise 13c: Draw Connection Lines (★★✩✩✩)

Write function draw_connections(node, line_length) for building a graphical output of the connection lines of a node to its two successors. Missing successors have to be handled correctly.

Tip

The line length refers to the characters between the node representations. The parts representing the ends are still to be appended appropriately in each case, as well as the middle connector.

Example

The following figure visualizes all cases relevant in drawing, so with none, one, and two successor(s):
                       F
           |-----------+-----------|
           D                       H
     |-----+                       +-----|
     B                                   I
  |--+--|
  A     C
A schematic representation is shown again in Figure 8-9.
Figure 8-9

Schematic representation of the connecting lines

Exercise 13d: Tree Representation (★★★★★)

Combine all solutions of the parts of the exercise and complete the necessary steps to be able to print an arbitrary binary tree suitably on the console. To do this, write function nice_print(node).

Example

The output of the tree shown in the introductory example should look something like this through nice_print():
                      F
          |-----------+-----------|
          D                       H
    |-----+                       +-----|
    B                                   I
 |--+--|
 A     C
Also, check your algorithm with a real monster of a tree, which you can find in the sources. Here is a much-slimmed-down representative:
                                     BIG
              |-----------------------+-----------------------|
             b2                                              f6
  |-----------+-----------|                     |-----------+-----------|
 a1                      d4                    d4                      g7
                    |-----+-----|         |-----+-----|
                   c3          f6        b2          e5
                             |--+--|   |--+--|
                            e5    g7  a1    c3

8.3 Solutions

8.3.1 Solution 1: Tree Traversal (★★✩✩✩)

Extend the functions already presented in the introduction for the traversing trees so that they can perform any action on the current node during the traversal. To do this, add an action to the respective signature, such as for inorder: inorder(node, action).

Algorithm With this extension, each method for traversing the tree receives an additional parameter to define an action. Then this is called at the appropriate place instead of the console output.
def inorder(node, action):
    if node is None:
        return
    inorder(node.left, action)
    action(node.item)
    inorder(node.right, action)
def preorder(node, action):
    if node is None:
        return
    action(node.item)
    preorder(node.left, action)
    preorder(node.right, action)
def postorder(node, action):
    if node is None:
        return
    postorder(node.left, action)
    postorder(node.right, action)
    action(node.item)

Bonus: Fill up a Tree into a List

Build a representation of the values of the nodes in the form of a list. To do this, write function to_list(node) that returns the values based on an inorder traversal, and functions to_list_preorder(node) and to_list_postorder(node) that are based on a preorder and postorder traversal, respectively.

Example

When using the following tree
           d4
      |-----+-----|
     b2          f6
  |--+--|      |--+--|
 a1    c3     e5    g7
the conversions should result in something similar to
to_list: ['a1', 'b2', 'c3', 'd4', 'e5', 'f6', 'g7']
to_list_preorder: ['d4', 'b2', 'a1', 'c3', 'f6', 'e5', 'g7']
to_list_postorder: ['a1', 'c3', 'b2', 'e5', 'g7', 'f6', 'd4']
Algorithm Instead of the console output used so far as an action, the current value is added depending on the chosen traversal strategy. For the recursive descent, you use += to add the partial results and the method append() from list for the value of the current node.
def to_list(start_node):
    if start_node is None:
        return []
    result = []
    result += to_list(start_node.left)
    result.append(startNode.item)
    result += to_list(start_node.right)
    return result
def to_list_preorder(start_node):
    if start_node is None:
        return []
    result = []
    result.append(start_node.item)
    result += to_list_preorder((start_node.left)
    result += to_list_preorder((start_node.right)
    return result
def to_list_postorder(start_node):
    if start_node is None:
        return []
    result = []
    result += to_list_postorder(start_node.left)
    result += to_list_postorder(start_node.right)
    result.append(start_node.item)
    return result

Verification

Define a tree, perform an inorder traversal with the action passed, and finally populate two more lists from the tree:
def main():
    def myprint(item):
        print(item, end=' ')
    root = example_trees.create_example_tree()
    TreeUtils.nice_print(root)
    print(" inorder with action:")
    inorder(root, myprint)
    print(" preorder with action:")
    preorder(root, myprint)
    print(" postorder with action:")
    postorder(root, myprint)
    print(" to_list:", to_list(root))
    print("to_list_preorder:", to_list_preorder(root))
    print("to_list_postorder:", to_list_postorder(root))
If you execute this main() function, you get the following output, which shows that your implementation works as expected:
          d4
     |-----+-----|
    b2          f6
  |--+--|     |--+--|
 a1    c3    e5    g7
inorder with action:
a1 b2 c3 d4 e5 f6 g7
preorder with action:
d4 b2 a1 c3 f6 e5 g7
postorder with action:
a1 c3 b2 e5 g7 f6 d4
to_list: ['a1', 'b2', 'c3', 'd4', 'e5', 'f6', 'g7']
to_list_preorder: ['d4', 'b2', 'a1', 'c3', 'f6', 'e5', 'g7']
to_list_postorder: ['a1', 'c3', 'b2', 'e5', 'g7', 'f6', 'd4']

8.3.2 Solution 2: Inorder, Preorder, and Postorder Iterative (★★★★✩)

In the introduction, you learned about inorder, preorder, and postorder as recursive variants. Now implement these types of traversals iteratively.

Example

Again, you use the following tree:
          d4
     |-----+-----|
    b2          f6
  |--+--|     |--+--|
 a1    c3    e5    g7
The three depth-first search methods traverse this tree as follows:
Preorder:   d4 b2 a1 c3 f6 e5 g7
Inorder:    a1 b2 c3 d4 e5 f6 g7
Postorder:  a1 c3 b2 e5 g7 f6 d4

Preliminary considerations for the algorithms For each of the iterative implementations, you need an auxiliary data structure. This is what I will now discuss in detail for the three variants.

Algorithm for inorder (★★★✩✩) When implementing an inorder traversal, you use a stack to temporarily store nodes that have to be processed later and variable current_node to store the current node. The basic idea is to start from the root, move to the bottom left of the tree, and put the current node on the stack until no successor is left. Then you take the uppermost node from the stack and process it (here by a simple console output). Now you continue with the right successor. Again, if there is no successor, process the top node from the stack.

The following sequence results for the tree of the example:

current_node

Stack

Action(s)

Direction of descent

d4

[ ]

Push d4

↙

b2

[d4]

Push b2

↙

a1

[b2, d4]

Push a1

↙

None

[a1, b2, d4]

Pop + action a1

↘

None

[b2, d4]

Pop + action b2

↘

c3

[d4]

Push c3

↙

None

[c3, d4]

Pop + action c3

↘

None

[d4]

Pop + action d4

↘

f6

[ ]

Push f6

↙

e5

[f6]

Push e5

↙

None

[e5, f6]

Pop + action e5

↘

None

[f6]

Pop + action f6

↘

g7

[ ]

Push g7

↙

None

[g7]

Pop + action g7

↘

None

[ ]

End

 
Based on this, the iterative implementation of inorder looks like this:
def inorder_iterative(start_node, action):
    if start_node is None:
        return
    nodes_to_process = Stack()
    current_node = start_node
    # are there still nodes on the stack or is the current node not None?
    while not nodes_to_process.is_empty() or current_node is not None:
        if current_node is not None:
            # recursive descent to the left
            nodes_to_process.push(current_node)
            current_node = current_node.left
        else:
            # no left successor, then process current node
            current_node = nodes_to_process.pop()
            action(current_node.item)
            # continue with right successor
            current_node = current_node.right
Algorithm for preorder (★★✩✩✩) Interestingly, preorder is quite simple because the root of a subtree is always processed first. Then the left and right subtree are processed. For this, you again use a stack, which you fill initially with the current node. As long as the stack is not empty, you determine the top element and execute the desired action. Then you place the left and right successor nodes on the stack if they exist. It is important to note that the order of adding is opposite to that of reading. For the left subtree to be processed first, you must put the right node on the stack before the left one. This is repeated until the stack is empty. The following sequence results for the tree of the example:

current_node

Stack

Action(s)

 

[d4]

Start: push d4

d4

[b2, f6]

Pop + action d4, push f6, push b2

b2

[a1, c3, f6]

Pop + action b2, push c3, push a1

a1

[c3, f6]

Pop + action a1

c3

[f6]

Pop + action c3

f6

[e5, g7]

pop + action f6, push g7, push e5

e5

[g7]

Pop + action e5

g7

[ ]

Pop + action g7

None

[ ]

End

This results in the following iterative preorder implementation, which is structurally very similar to the recursive variant:
def preorder_iterative(start_node, action):
    if start_node is None:
        return
    nodes_to_process = Stack()
    nodes_to_process.push(start_node)
    while not nodes_to_process.is_empty():
        current_node = nodes_to_process.pop()
        if current_node is not None:
            action(current_node.item)
            # so that left is processed first, here order is reversed
            nodes_to_process.push(current_node.right)
            nodes_to_process.push(current_node.left)

To keep the analogy as strong as possible, it is helpful that collections can also store None values. This allows you to perform the None check once when extracting from the stack and otherwise keep the source code free of special handling.

Algorithm for postorder (★★★★✩) With postorder, you also use a stack for the intermediate storage of the nodes to be processed later. Of the three, however, this algorithm is the one with the greatest challenges and is tricky to implement because with postorder, although the traversal starts at the root, the action has to be executed after visiting the left and right subtree. Therefore, you have an interesting change compared to the previous two algorithms. In them, if an element is taken from the stack, then it is processed and not touched again. With the postorder implementation, an element is potentially inspected twice or more with peek() and later on removed only after that.

This time, you’ll look at the source code first, and then I’ll give further explanations:
def postorder_iterative(start_node, action):
    if start_node is None:
        return
    nodes_to_process = Stack()
    current_node = start_node
    last_node_visited = None
    while not nodes_to_process.is_empty() or current_node is not None:
        if current_node is not None:
            # descent to the left
            nodes_to_process.push(current_node)
            current_node = current_node.left
        else:
            peek_node = nodes_to_process.peek()
            # descent to the right
            if peek_node.right is not None and
                last_node_visited != peek_node.right:
                current_node = peek_node.right
            else:
                # sub root or leaf processing
                last_node_visited = nodes_to_process.pop()
                action(last_node_visited.item)
This is how the process works.: You start with the root node, put it on the stack, and continue in the left subtree. You repeat this until you no longer find a left successor. Now you have to move to the right successor. Only after that may the root be processed. Since you have saved all nodes on the stack, you now inspect the node from the stack. If this one has no right children and you have not just visited it, then you execute the passed action and remember this node as the last visited. For the other case, that there is a right subtree, you also traverse it as just described. This procedure is repeated until the stack is empty.

current_node

Stack

peek_node

Action

d4

[d4]

 

Push d4

b2

[b2, d4]

 

Push b2

a1

[a1, b2, d4]

 

Push a1

None

[a1, b2, d4]

a1

Action a1

None

[b2, d4]

b2

Peek + right

c3

[c3, b2, d4]

 

Push c3

None

[c3, b2, d4]

c3

Action c3

None

[b2, d4]

b2

Action b2

f6

[f6, d4]

 

Push f6

e5

[e5, f6, d4]

 

Push e5

None

[f6, d4]

e5

Action e5

None

[f6, d4]

f6

Peek + right

g7

[g7, f6, d4]

 

Push g7

None

[g7, f6, d4]

g7

Action g7

None

[f6, d4]

f6

Action f6

None

[d4]

d4

Action d4

None

[ ]

  
NOTE: ITERATIVE IMPLEMENTATION OF POSTORDER

While the implementations of the three traversals’ recursive variants are all equally easy, and each is not very complex, this does not apply to the iterative implementations in any way. Preorder and inorder can still be implemented with a little thinking without major difficulties. With postorder, however, you really have to fight. Therefore, it is no shame to need a couple of attempts and to apply error corrections.

Don’t worry. It’s not always that tricky. Even the breadth-first traversal discussed later, which traverses level by level, is in my estimation much less complex to implement than the iterative postorder.

Recursion can be the key to simplicity in some cases. Sometimes, however, this comes at the expense of runtime. For optimization, you learned about memoization. However, very understandable iterative variants can also be found for some problems.

Verification

You define the tree from the introductory example and then traverse it each time using the desired procedure:
def main():
    def myprint(item):
        print(item, end=' ')
    root = example_trees.create_example_tree()
    TreeUtils.nice_print(root)
    print("inorder iterative:")
    inorder_iterative(root, myprint)
    print(" preorder iterative:")
    preorder_iterative(root, myprint)
    print(" postorder iterative:")
    postorder_iterative(root, myprint)
If you execute the above main() function, you get the following output, which shows that your implementation does what it is supposed to do:
             d4
        |-----+-----|
       b2          f6
     |--+--|     |--+--|
    a1    c3    e5    g7
inorder iterative:
a1 b2 c3 d4 e5 f6 g7
preorder iterative:
d4 b2 a1 c3 f6 e5 g7
postorder iterative:
a1 c3 b2 e5 g7 f6 d4
Verification with unit test As an example, and because the implementation has already demanded quite a bit from you, I show the test for postorder. The other two tests are analogous and can be found in the sources of the companion project. For the test, iteratively the current value is filled into a list. After processing all values, the resulting list is then checked against the expected values.
def test_postorder_iterative():
    root = example_trees.create_example_tree()
    result = []
    postorder_iterative(root, lambda item: result.append(item))
    assert result == ["a1", "c3", "b2", "e5", "g7", "f6", "d4"]

Surprise Algorithm

While preorder was quite easy to design iteratively, it became a bit more difficult with inorder and even really tricky with postorder.

But then I got a tip from Prof. Dr. Dominik Gruntz on how to simplify the entire process iteratively. Many thanks to Dominik for this great algorithm suggestion. You keep the sequences analogous to the recursive ones, however, in reverse order, since you work with a stack. Besides, you integrate artificial new tree nodes.
def inorder_iterative_v2(root):
    stack = Stack()
    stack.push(root)
    while not stack.is_empty():
        current_node = stack.pop()
        if not current_node is None:
            if current_node.is_leaf():
                print(current_node.item, end=" ")
            else:
                stack.push(current_node.right)
               stack.push(BinaryTreeNode(current_node.item))
                stack.push(current_node.left)
    print()
And better yet, you can turn it into a general-purpose function that allows all three traversal variations. To do this, you first define an enumeration and then the function traverse() that creates an artificial entry with a tree node at each appropriate point in the sequence. As mentioned, these special nodes ensure that the processing occurs at the right place.
class Order(Enum):
    PREORDER = auto()
    INORDER = auto()
    POSTORDER = auto()
def traverse(root, order):
    stack = Stack()
    stack.push(root)
    while not stack.is_empty():
        current_node = stack.pop()
        if not current_node is None:
            if current_node.is_leaf():
                print(current_node.item, end = " ")
            else:
                if order == Order.POSTORDER:
                    stack.push(BinaryTreeNode(current_node.item))
                 stack.push(current_node.right)
                if order == Order.INORDER:
                    stack.push(BinaryTreeNode(current_node.item))
                stack.push(current_node.left)
                if order == Order.PREORDER:
                    stack.push(BinaryTreeNode(current_node.item))
    print()
HINT: INSIGHT

With the help of this example, it is easy to grasp that thorough thinking about a problem can lead to simpler, more comprehensible, and less complex source code. Besides, it is always good to get a second or third opinion if a solution is more complex than desired.

8.3.3 Solution 3: Tree Height (★★✩✩✩)

Implement function get_height(node) to determine the height for both a tree and for subtrees with a single node as root.

Example

The following tree of height 4 is used as a starting point:
                    E
        |-----------+-----------|
        C                       G
  |-----|                 |-----+-----|
  A                       F           H
                                      |--|
                                         I
Algorithm The tree height calculation uses a recursive algorithm, which determines the height of the left and the right subtree. Finally, you must compute the maximum from this and then add the value 1 for the current level.
def get_height(parent):
    # recursive termination
    if parent is None:
        return 0
    # recursive descent
    left_height = get_height(parent.left)
    right_height = get_height(parent.right)
    return 1 + max(left_height, right_height)

Verification

You construct the tree from the example and then have the heights computed for some selected nodes:
def main():
    e = BinaryTreeNode("E")
    insert(e, "C")
    insert(e, "A")
    insert(e, "G")
    insert(e, "F")
    insert(e, "H")
    insert(e, "I")
    TreeUtils.nice_print(e);
    print_infos(e.left, e, e.right, e.right.right.right)
def print_infos(c, e, g, i):
    print(" Height of root E:", get\_height(e))
    print("Height from left parent C: ", get\_height(c))
    print("Height from right parent G:", get\_height(g))
    print("Height from right child I: ", get\_height(i))
The following output occurs:
                   E
       |-----------+-----------|
       C                       G
 |-----+                 |-----+-----|
 A                       F           H
                                     +--|
                                        I
Height of root E: 4
Height from left parent C: 2
Height from right parent G: 3
Height from right child I: 1

8.3.4 Solution 4: Lowest Common Ancestor (★★★✩✩)

Compute the lowest common ancestor (LCA) for two nodes, A and B, hosted in an arbitrary binary search tree. The LCA denotes the node that is the ancestor of both A and B and is located as deep as possible in the tree—the root is always the ancestor of both A and B. Write function find_lca(start_node, value1, value2) that, in addition to the start node of the search (usually the root), also receives lower and upper limits, which indirectly describe the nodes that are closest to these values. If the values for the limits are outside the range of values, then there is no LCA and it is supposed to return None.

Example

The following is a binary tree. If the lowest common ancestor is determined for the nodes with the values 1 and 5, this is the node with the value 4. In the figure, the respective nodes are circled and the ancestor is additionally marked in bold.
                        6
            |-----------+-----------|
           ➃                        7
      |-----+-----|
      2           ➄
   |--+--|
   ➀     3

Algorithm Intuitively, you may be tempted to go up from the two nodes until the paths cross. Nevertheless, this is impossible whenever no backward direction exists in the node to the parent—like here. However, in your modeling of trees using the BinaryTreeNode class, you only use references to children, not to the parent node.

But there is a straightforward implementation starting from the root. From there, you proceed as follows: Let current_value be the value of the current node. In addition, let value1 and value2 be the passed node values (i. e. those of the two nodes of the potential successors). If value1 and value2 are smaller than current_value, then due to the sorting property within the binary search tree, both must be located in the left subtree—continue searching there. If both value1 and value2 are greater than current_value, then continue searching on the right. Otherwise for the cases value1 < current_value < value2 or value2 < current_value < value1, you have found the LCA; it is the current node.
def find_lca(start_node, value1, value2):
    # recursive termination
    if start_node is None:
        return None
    current_value = start_node.item
    # recursive descent
    if value1 < current_value and value2 < current_value:
        return find_lca(start_node.left, value1, value2)
    if value1 > current_value and value2 > current_value:
        return find_lca(start_node.right, value1, value2)
    # Here is value1 < current_value < value2 or
    # value2 < current_value < value1
    return start_node

Verification

You construct the tree shown in the example and invoke your method:
@pytest.mark.parametrize("value1, value2, expected",
                         [(1, 3, 2), (1, 5, 4), (2, 5, 4),
                          (3, 5, 4), (1, 7, 6)])
def test_find_lca(value1, value2, expected):
    root = create_lca_example_tree()
    result = find_lca(root, value1, value2)
    assert result.item == expected
def test_find_lca_special():
    root = create_lca_example_tree()
    result = find_lca(root, 1, 2)
    assert result.item == 2

If you only check the quite obvious cases, everything works fine. If you consider checking two nodes in a parent-child relationship, namely the nodes with the values 1 and 2, you intuitively expect the node with the value 4. However, the node with the value 2 is calculated. According to the definition (among others in Wikipedia (https://en.wikipedia.org/wiki/Lowest_common_ancestor)), each node is also considered a successor of itself. Thus, the node with the value 2 is indeed the LCA in this case.

For the sake of completeness, the construction of the tree is shown:
def create_lca_example_tree():
    _6 = BinaryTreeNode(6)
    insert(_6, 7)
    insert(_6, 4)
    insert(_6, 5)
    insert(_6, 2)
    insert(_6, 1)
    insert(_6, 3)
    return _6

8.3.5 Solution 5: Breadth-First (★★★✩✩)

In this exercise, you are asked to implement the breadth-first search, also called level order, using the function levelorder(start_node, action). The breadth-first search starts at the given node—usually the root—and then works its way through the tree level by level.

Note

Use a queue to store data on the nodes yet to be visited. The iterative variant is a bit easier to implement than the recursive one.

Examples

For the following two trees, the sequence 1 2 3 4 5 6 7 (for the left) and M I C H A E L (for the right) are to be determined as the result.
            1                      M
      |-----+-----|          |-----+-----|
      2           3          I           C
   |--+--|     |--+--|    |--+--|     |--+--|
   4     5     6     7    H     A     E     L
Algorithm For the breadth-first search, you use a queue as a cache for nodes to be processed later. First, you insert the root into the queue. Then you process elements as long as there are elements in the queue. This processing is divided into steps. First, perform the desired action for each element. Then put the left and right successor nodes into the queue if such a node exists. The algorithm checks in the processing whether the value in the queue is not equal to None. This avoids the special handling of missing successors when adding them.
def levelorder(start_node, action):
    if start_node is None:
        return
    to_process = Queue()
    to_process.enqueue(start_node)
    while not to_process.is_empty():
        current = to_process.dequeue()
    if current is not None:
        action(current.item)
        to_process.enqueue(current.left)
        to_process.enqueue(current.right)

To avoid special handling and None checks in the source code as much as possible, you benefit from the fact that None values can be stored in containers. This allows you to run the None check once when removing from the queue and not check it when adding the child nodes.

Instead of the while loop, you can also solve this by using recursive calls. If you are interested, study the source code in the companion project.

Let’s clarify how the processes are in detail.

Queue

Action

[1]

1

[3, 2]

2

[5, 4, 3]

3

[7, 6, 5, 4]

4

[7, 6, 5]

5

[7, 6]

6

[7]

7

[ ]

End

Verification

You construct the tree with the numbers (the left one of the examples) and call your just created function to perform the level-order traversal:
def create_level_order_example_tree():
    _1 = BinaryTreeNode("1")
    _2 = BinaryTreeNode("2")
    _3 = BinaryTreeNode("3")
    _4 = BinaryTreeNode("4")
    _5 = BinaryTreeNode("5")
    _6 = BinaryTreeNode("6")
    _7 = BinaryTreeNode("7")
    _1.left = _2
    _1.right = _3
    _2.left = _4
    _2.right = _5
    _3.left = _6
    _3.right = _7
    return _1
def main():
    root = create_level_order_example_tree()
    tree_utils.nice_print(root)
    print("Levelorder: ")
    levelorder(root, lambda item: print(item, end=' '))
    print(" levelorder_recursive: ")
    levelorder_recursive(root, lambda item: print(item, end=' '))
Then you get the following output—please note that the project sources contain a recursive implementation of level-order too:
          1
    |-----+-----|
    2           3
 |--+--|     |--+--|
 4     5     6     7
Levelorder:
1 2 3 4 5 6 7
levelorder_recursive:
1 2 3 4 5 6 7
Verification with unit test This can also be expressed quite simply as a unit test:
def test_levelorder():
    root = create_level_order_example_tree()
    result = []
    levelorder(root, lambda item: result.append(item))
    assert result == ["1", "2", "3", "4", "5", "6", "7"]

8.3.6 Solution 6: Level Sum (★★★★✩)

In the previous exercise, you implemented the breadth-first search. Now you want to sum up the values per level of a tree. For this purpose, let’s assume that the values are natural numbers of type int. Write function level_sum(start_node).

Example

For the tree shown, the sums of the values of the nodes per level should be calculated and return the following result: {0=4, 1=8, 2=17, 3=16}.
                  4
      |-----------+-----------|
      2                       6
|-----+-----|           |-----+-----|
1           3           5           8
                                 |--+--|
                                 7     9

Level

Value(s)

Result

0

4

4

1

2, 6

8

2

1, 3, 5, 8

17

3

7, 9

16

Algorithm The breadth-first search provides a good basis. You are still missing a suitable data structure and a way to determine the current level to complete the solution. With a bit of thought, you come up with using a dictionary as the result data structure. The current level serves as the key. The value is formed by a tuple. You traverse the tree as you did with level order. To determine the levels, you cheat. Since you start from the root (of a subtree), you can assume level 0. Each change to a lower level increases the value. For this you use the second value from the tuple. This way, you always know on which level the currently processed node is located. With this information the summation can be formulated easily:
def level_sum(start_node):
    if start_node is None:
        return {}
    result = {}
    to_process = Queue()
    # pretty cool, tuple (node, level)
    to_process.enqueue((start_node, 0))
    while not to_process.is_empty():
        current_node_and_level = to_process.dequeue()
        current_node = current_node_and_level[0]
        level = current_node_and_level[1]
    if level not in result:
        result[level] = 0
    result[level] += current_node.item
    if current_node.left is not None:
        to_process.enqueue((current_node.left, level + 1))
    if current_node.right is not None:
        to_process.enqueue((current_node.right, level + 1))
    return result
Algorithm with depth-first search Interestingly, the same can be easily implemented using depth-first search, regardless of the type of traversal. In the following, it is implemented with inorder, and the variants for preorder and postorder are indicated as comments:
def level_sum_depth_first(root):
    results = {}
    traverse_depth_first(root, 0, results)
    return dict(sorted(results.items()))
def traverse_depth_first(current_node, level, results):
    if current_node:
        # PREORDER
        # results[level] = results.get(level, 0) + current_node.item
        traverse_depth_first(current_node.left, level + 1, results)
    # INORDER
    results[level] = results.get(level, 0) + current_node.item
    traverse_depth_first(current_node.right, level + 1, results)
    # POSTORDER
    # results[level] = results.get(level, 0) + current_node.item

As before, you use a dictionary as a data structure, whose key is the level. If there is already an entry for the level, the value of the current node is added. Otherwise, the trick of specifying a default value in the call get(level, 0) ensures a starting value of 0.

Verification

Let’s construct the tree from the example as usual and invoke the function you just implemented:
def main():
    root = create_example_level_sum_tree()
    result = level_sum(root)
    print(" level_sum:", result)
def create_example_level_sum_tree():
    _4 = BinaryTreeNode(4)
    insert(_4, 2)
    insert(_4, 1)
    insert(_4, 3)
    insert(_4, 6)
    insert(_4, 5)
    insert(_4, 8)
    insert(_4, 7)
    insert(_4, 9)
    return _4
Then you get the following output:
                        4
           |-----------+-----------|
           2                       6
     |-----+-----|           |-----+-----|
     1           3           5           8
                                      |--+--|
                                      7     9
level_sum: {0=4, 1=8, 2=17, 3=16}
Verification with unit test This can also be expressed quite simply as a unit test:
def test_level_sum():
    root = create_example_level_sum_tree()
    result = level_sum(root)
    assert result == {0: 4, 1: 8, 2: 17, 3: 16}
def test_level_sum_depth_first():
    root = create_example_level_sum_tree()
    result = level_sum_depth_first(root)
    assert result == {0: 4, 1: 8, 2: 17, 3: 16}

8.3.7 Solution 7: Tree Rotate (★★★✩✩)

Binary trees, especially binary search trees, may degenerate into lists if values are inserted only in ascending or descending order. A dysbalance can be addressed by rotating parts of the tree. Write functions rotate_left(node) and rotate_right(node) that will rotate the tree around the node passed as parameter to the left or right, respectively.

Example

Figure 8-10 visualizes a rotation to the left and a rotation to the right with the balanced starting position in the middle.
Figure 8-10

Rotation to the left, original, rotation to the right

Algorithm At first, you might be frightened by the expected, but in fact only supposed, complexity of the undertaking. In general, it is a good idea to mentally go through the process using a simple example, such as the one above. Quite quickly you will realize that far fewer nodes are involved and actions are necessary than probably expected. To execute the respective rotation, you actually only have to consider the root and the left or right neighbor as well as a node from the level below, as shown in Figure 8-11.
Figure 8-11

Nodes affected during rotations

Figure 8-11 illustrates that you just need to reassign two links in the tree to complete the rotation. To gain a better understanding of this, the relevant nodes are named accordingly. In the figure, LC and RC stand for Left Child and Right Child, LLC and LRC for Left Left Child and Left Right Child, and RLC and RRC for Right Left Child and Right Right Child.

With these preliminary considerations, the implementation of the rotations exactly follows the sequence illustrated in the diagrams:
def rotate_left(node):
    if node.right is None:
        raise ValueError("can't rotate left, no valid root")
    rc = node.right
    rlc = node.right.left
    rc.left = node
    node.right = rlc
    return rc
def rotate_right(node):
    if node.left is None:
        raise ValueError("can't rotate right, no valid root")
    lc = node.left
    lrc = node.left.right
    lc.right = node
    node.left = lrc
    return lc

Please keep in mind that these functions change the subtrees’ references and thus may affect previously cached nodes. The root is suddenly no longer the root but located one level below.

Verification

First, you define the tree in the middle, like the example. Then you rotate it first to the left and then twice to the right, which should correspond to a simple rotation to the right starting from the tree in the middle.
def main():
    root = example_trees.create_example_tree()
    TreeUtils.nice_print(root)
    print(" Rotate left")
    left_rotated_root = rotate_left(root)
    TreeUtils.nice_print(left_rotated_root)
    print(" Rotate right")
    right_rotated_root = rotate_right(rotate_right(left_rotated_root))
    TreeUtils.nice_print(right_rotated_root)
Execute the program to see that the rotations work correctly:
            d4
       |-----+-----|
      b2          f6
    |--+--|     |--+--|
   a1    c3    e5    g7
Rotate left
                    f6
         |-----------+-----------|
        d4                      g7
   |-----+-----|
  b2          e5
|--+--|
a1   c3
Rotate right
                       b2
            |-----------+-----------|
           a1                      d4
                              |-----+-----|
                             c3          f6
                                       |--+--|
                                      e5    g7
Verification with unit test Let’s consider how you could test this using unit tests. Again, it depends on the appropriate idea and data structure. It would be difficult and costly to check the resulting trees for consistency structurally. It is much easier if you compare the result of a traversal with the expected values. But pay attention. When doing this, you have to avoid using the inorder traversal since it always produces the same node order for an arbitrary binary search tree, regardless of the tree’s structure! Here either a preorder or a postorder or, better still, a level order traversal is suitable. The latter has the great advantage that the order can be easily derived from a graphical representation of the tree and is, therefore, best suited for the unit test because it remains comprehensible and understandable. You already implemented the conversion at the beginning in Section 8.1.4 as method convert_to_list().
def test_rotate_left():
    root = example_trees.create_example_tree()
    result = rotate_left(root)
    as_list = convert_to_list(result)
    assert as_list == ["f6", "d4", "g7", "b2", "e5", "a1", "c3"]
def test_rotate_right():
    root = example_trees.create_example_tree()
    result = rotate_right(root)
    as_list = convert_to_list(result)
    assert as_list == ["b2", "a1", "d4", "c3", "f6", "e5", "g7"]
As a reminder, the function for converting a tree into a list based on a level order is shown here again.
def convert_to_list(node):
    result = []
    levelorder(node, lambda item: result.append(item))
    return result

8.3.8 Solution 8: Reconstruction (★★★✩✩)

Solution 8a: Reconstruction from a List (★★✩✩✩)

In this exercise, you want to reconstruct a binary search tree that is as balanced as possible from an ascending sorted list of natural numbers.

Example

For example, use these values:
values = [1, 2, 3, 4, 5, 6, 7]
Then the following tree should be reconstructed from them:
            4
      |-----+-----|
      2           6
   |--+--|     |--+--|
   1     3     5     7
Algorithm Reconstructing a binary search tree from a sorted list in ascending order is not that difficult. Due to the sorting, you can split the list in half and use the value in the middle as the base for the new node. You construct the left and right subtree recursively from the list’s left and right parts, respectively. You continue the bisection until the sublist has only the size 0 or 1.
def reconstruct(values):
    # recursive termination
    if not values: # len(values) == 0 not recommended by PEP 8
        return None
    mid_idx = len(values) // 2
    mid_value = values[mid_idx]
    new_node = BinaryTreeNode(mid_value)
    # recursive termination
    if len(values) == 1:
        return new_node
    # recursive descent
    left_part = values[0: mid_idx]
    right_part = values[mid_idx + 1:len(values)]
    new_node.left = reconstruct(left_part)
    new_node.right = reconstruct(right_part)
    return new_node

You could omit the query on length 1 in the middle of the function without changing the functionality. The function would then simply be called twice for an empty list and thus terminate directly. For me, this special treatment was a bit more understandable, but that’s a matter of taste.

Verification

Let’s see the implementation in action and supply an arbitrary but suitably sorted list of int values. With this, you invoke your function, which returns the root of the tree as a result. Finally, you verify that the tree is indeed correctly reconstructed by printing various information to the console.
def main():
    inputs = [[1, 2, 3, 4, 5, 6, 7],
             [1, 2, 3, 4, 5, 6, 7, 8]]
    for values in inputs:
        root = reconstruct(values)
        print_info(root)
The output function is simple to implement:
def print_info(root):
    TreeUtils.nice_print(root)
    print("Root: ", root)
    print("Left: ", root.left)
    print("Right:", root.right)
    print()
The following abbreviated output shows that the two trees are correctly reconstructed:
          4
    |-----+-----|
    2           6
 |--+--|     |--+--|
 1     3     5     7
Root:  BinaryTreeNode [item=4, left=BinaryTreeNode [item=2, ..
Left:  BinaryTreeNode [item=2, left=BinaryTreeNode [item=1, ...
Right: BinaryTreeNode [item=6, left=BinaryTreeNode [item=5, ...
                       5
           |-----------+-----------|
           3                       7
     |-----+-----|           |-----+-----|
     2           4           6           8
  |--|
  1
Root:  BinaryTreeNode [item=5, left=BinaryTreeNode [item=3, ...
Left:  BinaryTreeNode [item=3, left=BinaryTreeNode [item=2, ...
Right: BinaryTreeNode [item=7, left=BinaryTreeNode [item=6, ...
Verification with unit test Once again you use a level order traversal for the unit test to verify the reconstruction:
def test_reconstruct_from_list():
    inputs = [1, 2, 3, 4, 5, 6, 7]
    result_root = reconstruct(inputs)
    result = convert_to_list(result_root)
    assert result == [4, 2, 6, 1, 3, 5, 7]

Solution 8b: Reconstruction from Inorder/Preorder (★★★✩✩)

Suppose the sequence of values in preorder and inorder is given, each prepared as a list. This information about an arbitrary binary tree should be used to reconstruct the corresponding tree. Write function reconstruct(preorder_values, inorder_values).

Example

Two sequences of values of the traversals are given below. Based on these values, you should reconstruct the tree shown in the previous part of the exercise.
preorder_values = [4, 2, 1, 3, 6, 5, 7]
inorder_values = [1, 2, 3, 4, 5, 6, 7]
Algorithm For a better understanding of the need for two inputs and the algorithm, let’s take another look at the values of a preorder and inorder traversal with the value of the root highlighted in bold as an example:
Preorder  4 2 1 3 6 5 7
Inorder   1 2 3 4 5 6 7
The preorder traversal always starts with the root, so based on the first value, you can create the root first. By searching for the value of the root in the value sequence of the inorder traversal, you determine how the values are divided into left and right subtrees. Everything in the inorder to the left of the value of the root represents the values of the left subtree. Analogously, this applies to the values to the right of it and the right subtree. This results in the following sublists:
Left:  1 2 3
Right: 5 6 7

To call your function recursively, you need to find the corresponding value sequences for preorder. How do you do this?

Let’s take a detailed look at the values of a preorder and an inorder traversal. By looking closely, you can see the following pattern:
$$ {displaystyle egin{array}{l}; preorder;overset{root}{overbrace{4}} overset{left}{overbrace{213}} overset{right}{overbrace{657}}\ {} Inorderkern0.36em underset{left}{underbrace{;123}}kern0.24em underset{root}{underbrace{4}}kern0.24em underset{right}{underbrace{567}}end{array}} $$
With this knowledge, you can implement the algorithm as follows, taking advantage of slicing to generate the appropriate chunks from the original and use them for the recursive descent:
def reconstruct_clearer(preorder_values, inorder_values):
    # recursive termination
    # len(values) == 0 not recommended by PEP 8
    if not preorder_values or not inorder_values:
        return None
    root_value = preorder_values[0]
    root = BinaryTreeNode(root_value)
    # recursive termination
    if len(preorder_values) == 1 and len(inorder_values) == 1:
        return root
    # recursive descent
    index = inorder_values.index(root_value)
    # left and right part for inorder
    left_inorder = inorder_values[0: index]
    right_inorder = inorder_values[index + 1: len(inorder_values)]
    # left and right part for preorder
    left_preorder = preorder_values[1: 1 + index]
    right_preorder = preorder_values[index + 1: len(preorder_values)]
    root.left = reconstruct_clearer(left_preorder, left_inorder)
    root.right = reconstruct_clearer(right_preorder, right_inorder)
    return root

Verification

To understand the reconstruction, you provide the appropriate value sequences as three nested lists. As usual, Pytest automatically extracts the preorder and inorder values from each of these inputs. The result is given in the form of a level order traversal. This offers good traceability based on the graphical representation.
@pytest.mark.parametrize("preorder_values, inorder_values, expected",
                         [([4, 2, 1, 3, 6, 5, 7], [1, 2, 3, 4, 5, 6, 7],
                           [4, 2, 6, 1, 3, 5, 7]),
                          ([5, 4, 2, 1, 3, 7, 6, 8], [1, 2, 3, 4, 5, 6, 7, 8],
                           [5, 4, 7, 2, 6, 8, 1, 3])])
def test_reconstruct_from_pre_in_order(preorder_values, inorder_values,
                                       expected):
    result_root = reconstruct_clearer(preorder_values, inorder_values)
    result = convert_to_list(result_root)
    assert result == expected
HINT: THINGS TO KNOW ABOUT RECONSTRUCTION
Interestingly, using the algorithm shown, any binary tree can be reconstructed, regardless of whether it is also a binary search tree (for which its nodes follow an order). But it gets even more remarkable. If the values of the preorder traversal originate from a binary search tree, it is possible to reconstruct it based only on that, as follows:
def reconstruct_from_preorder_bst(preorder_values):
    # recursive termination
    if not preorder_values:
        return None
    root_value = preorder_values[0]
    root = BinaryTreeNode(root_value)
    # splitting
    left_values = [value for value in preorder_values if value < root_value]
    right_values = [value for value in preorder_values if value > root_value]
    # recursive descent
    root.left = reconstruct_from_preorder_bst(left_values)
    root.right = reconstruct_from_preorder_bst(right_values)
    return root

This is possible since, in a binary search tree, the values of the preorder traversal are first the value of the root, then the values smaller than the root, and finally the values of the right subtree, which are also larger than the value of the root. This condition also applies recursively. With the help of two filter conditions, all left and right subtree values can be easily extracted—as shown above—and used as input for the recursive call.

Try the reconstruction with the following dataset:
inputs = [[4, 2, 1, 3, 6, 5, 7],
          [5, 4, 2, 1, 3, 7, 6, 8]]
for values in inputs:
    root = reconstruct_from_preorder_bst(values)
    TreeUtils.nice_print(root)
The first input data generates the following tree:
              4
        |-----+-----|
        2           6
     |--+--|     |--+--|
     1     3     5     7

8.3.9 Solution 9: Math Evaluation (★★✩✩✩)

Consider using a tree to model mathematical expressions with the four operators +, −, /, and ∗. It is your task to compute the value of individual nodes, including in particular the value of the root node. For this purpose, write function evaluate(node).

Example

Represent the expression 3 + 7 ∗ (7 − 1) by the following tree to compute the value 45 for the root node:
                      +
          |-----------+-----------|
          3                       *
                            |-----+-----|
                            7           -
                                     |--+--|
                                     7     1
Algorithm The problem can be solved simply and clearly by a recursive call in combination with the appropriate operators as follows. It’s a bit clumsy due to the fact that there is no switch in Python up to Python 3.9.
def evaluate(node):
    value = node.item;
    if value == "+":
        return evaluate(node.left) + evaluate(node.right)
    if value == "-":
        return evaluate(node.left) - evaluate(node.right)
    if value == "*":
       return evaluate(node.left) * evaluate(node.right)
    if value == "/":
       return evaluate(node.left) / evaluate(node.right)
    else:
       return int(value)
Python 3.10 introduces match as a new keyword, which is more powerful than switch known from other programming languages. In combination with a dynamic evaluation, you can write the whole thing as follows:
def evaluate_v2(node):
    value = node.item
    match value:
        case "+" | "-" | "*" | "/":
            val1 = evaluate_v2(node.left)
            val2 = evaluate_v2(node.right)
            return eval(str(val1) + value + str(val2))
        case _:
            return int(value)

Verification

Let’s construct the tree from the example and invoke the above function:
def main():
    plus = BinaryTreeNode("+")
    _3 = BinaryTreeNode("3")
    mult = BinaryTreeNode("*")
    _7 = BinaryTreeNode("7")
    minus = BinaryTreeNode("-")
    _1 = BinaryTreeNode("1")
    plus.left = _3
    plus.right = mult
    mult.left = _7
    mult.right = minus
    minus.left = _7
    minus.right = _1
    tree_utils.nice_print(plus)
    print("+:", evaluate(plus))
    print("*:", evaluate(mult))
    print("-:", evaluate(minus))
    print("+:", evaluate_v2(plus))
    print("*:", evaluate_v2(mult))
    print("-:", evaluate_v2(minus))
If you execute this main() function, you get on the output of the tree as well as the results of the selected individual nodes:
              +
  |-----------+-----------|
  3                       *
                    |-----+-----|
                    7           -
                             |--+--|
                             7     1
+: 45
*: 42
-: 6
+: 45
*: 42
-: 6

8.3.10 Solution 10: Symmetry (★★✩✩✩)

Check if an arbitrary binary tree is symmetric in its structure. Write function is_symmetric(node). In addition to the structural examination, you can also check for equality of values.

Examples

To check for symmetry, you use a binary tree that is symmetric in structure (left) and a binary tree that is also symmetric concerning values (right).
            4                      1
      |-----+-----|              /  
     2            6             2    2
  |--+--|      |--+--|         /      
  1     3      5     7         3       3
NOTE: THE SYMMETRY PROPERTY
In a symmetric binary tree, the left and right subtree are mirrored through the root along an imaginary vertical line (indicated by |):
      1
     /|
    2 | 2
   /  |  
  3   |   3

Depending on the definition, a comparison of the values can be omitted for the symmetry. In this case, only the structural organization can be counted as relevant.

Algorithm Once again, you benefit from a good basic knowledge of recursion. Starting from the root, you check the two opposite successor nodes. The simplest case is that for a node, no successor nodes exist. This constellation is always symmetrical. If, however, only one of the two successor nodes exists, then the tree is not symmetric. Accordingly, only the case for two successor nodes is to be considered. Here the respective left and right subtrees must be mirror-inverted. For this, you check recursively whether the right subtree of the left and the left subtree of the right node structurally fit each other, as well as the left subtree of the right and the right subtree of the left node.
def is_symmetric(node):
    if node is None:
        return True
    return check_if_nodes_are_symmetric(node.left, node.right)
def check_if_nodes_are_symmetric(left, right):
    if left is None and right is None:
        return True
    if left is None or right is None:
        return False
    # descend both subtrees
    return check_if_nodes_are_symmetric(left.right, right.left) and
        check_if_nodes_are_symmetric(left.left, right.right)
Advanced algorithm: Value symmetry In fact, the extension to value checking is simple if you have implemented the previous exercise correctly. Only a Boolean parameter check_value has to be added to the signature and evaluated at the appropriate place before the recursive descent:
def check_if_nodes_and_values_are_symmetric(left, right, check_value):
    if left is None and right is None:
        return True
    if left is None or right is None:
        return False
    # check values
    if check_value and not left.item == right.item:
        return False
    # descend both subtrees
    return check_if_nodes_and_values_are_symmetric(left.right, right.left,
                                                   check_value) and
            check_if_nodes_and_values_are_symmetric(left.left, right.right,
                                                   check_value)

Verification

You construct the two trees from the introduction and invoke the function you just created. The first tree is already known. The other one is explicitly created for this example with create_symmetric_number_tree(): After that, you add the node with the value 4, which deliberately breaks the symmetry.
def main():
    root = example_trees.create_number_tree()
    TreeUtils.nice_print(root)
    print("symmetric:", is_symmetric(root))
    root2 = create_symmetric_number_tree()
    TreeUtils.nice_print(root2)
    print("symmetric:", is_symmetric(root2))
    # modified tree: add a 4
    root2.right.left = BinaryTreeNode("4")
    TreeUtils.nice_print(root2)
    print("symmetric:", is_symmetric((root2))
In create_symmetric_number_tree() you create a root and then the symmetric structure with nodes with the values 2 and 3.
def create_symmetric_number_tree():
    root = BinaryTreeNode("1")
    root.left = BinaryTreeNode("2")
    root.right = BinaryTreeNode("2")
    root.left.left = BinaryTreeNode("3")
    root.right.right = BinaryTreeNode("3")
    return root
If you execute this main() function, you get the expected results:
           4
     |-----+-----|
     2           6
  |--+--|     |--+--|
  1     3     5     7
symmetric: True
            1
      |-----+-----|
      2           2
   |--+           +--|
   3                 3
symmetric: True
           1
     |-----+-----|
     2           2
  |--+        |--+--|
  3           4     3
symmetric: False

Bonus: Mirror Tree

In the hint box, I indicated a mirror axis through the root. Create function invert(node) that mirrors the nodes of a tree at this implied line through the root.

Example

A mirroring looks like this:
            4                      4
      |-----+-----|          |-----+-----|
      2           6    =>    6           2
   |--+--|     |--+--|    |--+--|     |--+--|
   1     3     5     7    7     5     3     1

Algorithm At first, you might once again assume that the challenge is difficult to solve. But in fact, it is much easier to implement with the help of recursion than you initially think.

The algorithm proceeds from the root downwards and swaps the left and right subtrees. To do this, you store these subtrees in temporary variables and then assign them to the other side. That’s really all there is to it!

You implement this in Python as follows:
def invert(root):
    if root is None:
        return None
    inverted_right = invert(root.right)
    inverted_left = invert(root.left)
    root.left = inverted_right
    root.right = inverted_left
    return root
Python shortcut Using the tuple notation, you can implement the whole thing even more compactly as follows:
def invert_clearer(root):
    if root is None:
        return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root

Verification

You construct the left tree from the introduction and invoke the function you just created:
def main():
    root = example_trees.create_number_tree()
    newroot = invert(root)
    TreeUtils.nice_print(newroot)
    newroot = invert_clearer(newroot)
    TreeUtils.nice_print(newroot)
If you execute this main() function, you get the expected mirroring and another one results again in the original:
               4
         |-----+-----|
         6           2
      |--+--|     |--+--|
      7     5     3     1
               4
         |-----+-----|
         2           6
      |--+--|     |--+--|
      1     3     5     7

8.3.11 Solution 11: Check Binary Search Tree (★★✩✩✩)

In this exercise, you check whether an arbitrary binary tree fulfills the property of a binary search tree (BST), so the values in the left subtree are smaller than the root node’s value and those in the right subtree are larger—and this holds for each subtree starting from the root. For simplification, assume int values. Write function is_bst(node).

Example

Use the following binary tree, which is also a binary search tree. For example, if you replace the number 1 with a larger number on the left side, it is no longer a binary search tree. However, the right subtree under the 6 is still a binary search tree.
          4
    |-----+-----|
    2           6
 |--+--|     |--+--|
 1     3     5     7
Algorithm From the assignment, you recognize a recursive design. A tree with only one node is always a binary search tree. If there is a left or right successor or even both, you check their values for compliance with the value relation and perform this recursively for their successors, if they exist.
def is_bst(node):
    # recursive termination
    if node is None:
        return True
    if node.is_leaf():
        return True
    # recursive descent
    is_left_bst = True
    is_right_bst = True
    if node.left is not None:
        is_left_bst = node.left.item < node.item and is_bst(node.left)
    if node.right is not None:
        is_right_bst = node.right.item > node.item and is_bst(node.right)
    return is_left_bst and is_right_bst

Verification

You construct the tree from the example and invoke the function you just created. You also apply two modifications and check again.
def main():
    _4 = create_integer_number_tree()
    _2 = _4.left
    _6 = _4.right
    TreeUtils.nice_print(_4)
    print("is_bst(_4):", is_bst(_4))
    print("is_bst(_2):", is_bst(_2))
    print("is_bst(_6):", is_bst(_6))
    # change the tree on the left in a wrong and on the right in a correct way
    _2.left = BinaryTreeNode(13)
    _6.right = None
    TreeUtils.nice_print(_4)
    print("is_bst(_4):", is_bst(_4))
    print("is_bst(_2):", is_bst(_2))
    print("is_bst(_6):", is_bst(_6))

If you execute this main() function, you get both the output of the tree and the results for selected individual nodes, whether these nodes themselves (but of course with their successors) represent a binary search tree.

However, if you carelessly store a larger value in the left subtree (e. g., 13), neither the whole tree nor the part with node 2 as root is a BST. For the right subtree, if you delete the node with the value 7, the right subtree with the node with the value 6 remains a BST.
                4
          |-----+-----|
          2           6
       |--+--|     |--+--|
       1     3     5     7
is_bst(_4): True
is_bst(_2): True
is_bst(_6): True
            4
      |-----+-----|
      2           6
   |--+--|     |--|
  13     3     5
is_bst(_4): False
is_bst(_2): False
is_bst(_6): True

8.3.12 Solution 12: Completeness (★★★★★)

In this exercise, you check the completeness of a tree. To do this, you initially solve the basics in the first two parts of the exercise and then proceed to the trickier completeness check.

Solution 12a: Number of Nodes (★✩✩✩✩)

Count how many nodes are contained in any binary tree. To do this, write function count_nodes(node).

Example

For the binary tree shown, the value 7 should be determined. If you remove the right subtree, the tree consists of only 4 nodes.
          4
    |-----+-----|
    2           6
 |--+--|     |--+--|
 1     3     5     7
Algorithm The algorithm is really extremely straightforward if you express it recursively. Each node counts as 1, and then you continue counting in both its left and right subtrees and add their results until you hit a leaf.
def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

Solution 12b: Check for Full/Perfect (★★✩✩✩)

For an arbitrary binary tree, check if all nodes have two successors or leaves each, and thus the tree is full. For perfection, all leaves must be at the same height. Write functions is_full(node) and is_perfect(node).

Example

The binary tree shown is both perfect and full. If you remove the two leaves below the 2, it is no longer perfect but still full.
   Full and perfect          Full but not perfect
         4                           4
   |-----+-----|               |-----+-----|
   2           6               2           6
|--+--|     |--+--|                     |--+--|
1     3     5     7                     5     7
Algorithm The check whether a tree is full is not that difficult if it is implemented recursively. Attention: Please do not confuse full and complete (see the introduction for definitions). A tree is full if it has no or two successors. Otherwise, it cannot be a full tree.
def is_full(node):
    if node is None:
        return True
    return __is_full_helper(node.left, node.right)
def __is_full_helper(left_node, right_node):
    if left_node is None and right_node is None:
        return True
    if left_node is not None and right_node is not None:
        return is_full(left_node) and is_full(right_node)
    return False
This is a good start. Based on this, you need some smaller extensions to be able to check the perfectness. First, you must determine the height of the whole tree, starting from the root. This can easily be achieved, as you implemented it as solution of Exercise 8.3.3. After that, you proceed quite similar to is_full(), but now every node must have two successors. On the level of the leaves, you additionally have to check if they are at the correct level. You might stumble over the fact that the height of a leaf is 1. Therefore you still need the level on which they are located. For this, you cheat with an additional parameter current_level in your function. This results in the following implementation:
def is_perfect(node):
    if node is None:
        return True
    height = get_height(node)
    return is_perfect_helper(node.left, node.right, height, 1)
def is_perfect_helper(left_node, right_node, height, current_level):
    if left_node is None or right_node is None:
        return False
    if left_node.is_leaf() and right_node.is_leaf():
        return on_same_height(left_node, right_node, height, current_level)
    return is_perfect_helper(left_node.left, left_node.right, height,
                             current_level + 1) and
        is_perfect_helper(right_node.left, right_node.right, height,
                          current_level + 1)
def on_same_height(left_node, right_node, height, current_level):
    # problem: height of the node is 1, therefore you must
    # take into account the current level here
    return get_height(left_node) + current_level == height and
        get_height(right_node) + current_level == height

Verification

You construct the tree with numbers from the introduction and invoke the methods you just created. In addition, you modify the tree by deleting the reference to the right subtree. Then you invoke the functions again.
def main():
    _4 = example_trees.create_number_tree()
    TreeUtils.nice_print(_4)
    print("#nodes:", count_nodes(_4))
    print("is_full?:", is_full(_4))
    print("is_perfect?:", is_perfect(_4))
    print()
    # delete nodes with values 1, 3
    _2 = _4.left
    _2.left = None
    _2.right = None
    TreeUtils.nice_print(_4)
    print("#nodes:", count_nodes(_4))
    print("is_full?:", is_full(_4))
    print("is_perfect?:", is_perfect(_4))
    print()
If you run this main() function, you get the expected results:
                4
          |-----+-----|
          2           6
       |--+--|     |--+--|
       1     3     5     7
#nodes: 7
is_full?: True
is_perfect?: True
              4
        |-----+-----|
        2           6
                 |--+--|
                 5     7
#nodes: 5
is_full?: True
is_perfect?: False

Solution 12c: Completeness (★★★★✩)

In this subtask, you check if a tree is complete as defined in the introduction—as a binary tree with all levels fully filled, with the allowed exception on the last level where nodes may be missing, but only with gaps as far to the right as possible.

Example

In addition to the perfect tree used so far, the following tree is also complete by definition. However, if you remove the children from node H, the tree is no longer complete.
                      F
          |-----------+-----------|
          D                       H
    |-----+-----|           |-----+-----|
    B           E           G           I
 |--+--|
 A     C

Algorithm At first, this seems to be a rather tricky task, much more complicated than the checks shown before. If you study the definition again, the tree is supposed to contain successors in pairs. Moreover, there must be no gaps in the tree, so no node with a missing left successor but with a right successor. If the tree is not fully filled, then only leaves from the right may be missing. On closer visual inspection, it is noticeable that you can traverse level by level, but nodes may be missing only in the last level.

Now the level order traversal comes to mind. You use this here and just add a few checks. For each node there must be no right successor without a left one. Besides, you check whether you have discovered a missing node in the meantime. How can this happen? This is possible whenever you want to add a node’s successors to the queue, but there is only one left or right successor. This is expressed by the flag missing_node. So, if a missing successor has been detected, then the nodes processed afterwards must be leaves only.
def levelorder_is_complete(start_node):
    if start_node is None:
        return False
    to_process = Queue()
    to_process.enqueue(start_node)
    # indicates that a node does not have two successors
    missing_node = False
    while not to_process.is_empty():
        current = to_process.dequeue()
        # only descendants on the right side
        if current.left is None and current.right is not None:
            return False
        # if a missing node was previously detected,
        # then the next may be only a leaf
        if missing_node and not current.is_leaf():
             return False
        # include sub-elements, mark if not complete
        if current.left is not None:
             to_process.enqueue(current.left)
        else:
             missing_node = True
        if current.right is not None:
             to_process.enqueue(current.right)
        else:
             missing_node = True
    # all nodes successfully tested
    return True

Verification

You construct the tree from the example and invoke the function you just created. In addition, you modify the tree by removing the leaves below the H node and check again.
def main():
    F = create_completness_example_tree()
    TreeUtils.nice_print(F)
    print("levelorder_is_complete?", levelorder_is_complete(F))
    # remove leaves under H
    H = F.right
    H.left = None
    H.right = None
    TreeUtils.nice_print(F)
    print("levelorder_is_complete?", levelorder_is_complete(F))
def create_completness_example_tree():
    F = BinaryTreeNode("F")
    TreeUtils.insert(F, "D")
    TreeUtils.insert(F, "H")
    TreeUtils.insert(F, "B")
    TreeUtils.insert(F, "E")
    TreeUtils.insert(F, "A")
    TreeUtils.insert(F, "C")
    TreeUtils.insert(F, "G")
    TreeUtils.insert(F, "I")
    return F
If you execute this main() function, you get the expected results:
                         F
             |-----------+-----------|
             D                       H
       |-----+-----|           |-----+-----|
      B            E          G            I
   |--+--|
   A     C
levelorder_is_complete? True
                        F
            |-----------+-----------|
            D                       H
      |-----+-----|
      B           E
   |--+--|
   A     C
levelorder_is_complete? False

Solution 12d: Completeness Recursive (★★★★★)

In this last subtask, the following challenge remains to be mastered as a special treat. The check is to be solved without additional data structures and purely recursively. At first, this sounds hardly feasible, so I’ll give a hint.

Tip

Develop the solution step by step. Create an auxiliary data structure that models whether or not a node exists for a certain position. Then traverse the tree and mark the positions appropriately. Afterwards, convert this implementation to a purely recursive one without the auxiliary data structure.

Example

As before, the following tree is complete by definition:
                         F
             |-----------+-----------|
             D                       H
       |-----+-----|           |-----+-----|
       B           E           G           I
    |--+--|
    A     C

Algorithm In fact, the assignment sounds hardly manageable, but that is why it is a tough challenge. As like so often, it is worthwhile to start by developing a version that does not yet meet all the required properties and gradually refine it. You start with the ideas from the tip.

The idea is this: You traverse the tree, and for each node that exists, you mark exactly that in a list of bools When doing so, you number the positions according to level order from left to right and top to bottom. To determine the position of the current node in the list, you perform the following computation: For the position i, the left successor has the position i ∗ 2 + 1 and the right successor has position i ∗ 2 + 2.3 Figure 8-12 illustrates this.
Figure 8-12

Map a tree node to a position in the list/array

Now you still need to know how large the result list needs to be. Theoretically, at most, it can contain 2height elements. However, for very deep and thus expanding trees, many leaves might not exist at all. To optimize the memory consumption, you count the number of nodes to determine the actual size needed. This is where Exercise 12a helps you. Then you traverse all the tree elements using the traverse_and_mark() function. Finally, you summarize the data using all_assigned().
def is_complete(start_node):
    node_count = count_nodes(start_node)
    node_exists = [False] * node_count
    # now you traverse the tree from the root downwards
    traverse_and_mark(start_node, node_exists, 0)
    return all_assigned((node_exists)
Let’s move on to traversing the tree and filling the list. Interestingly, it doesn’t matter whether you use preorder, inorder, or postorder here. The only important thing is that the positions are determined according to the mentioned computation rule.
def traverse_and_mark(start_node, node_exists, pos):
    # recursive termination
    if start_node is None:
        return
    if pos >= len(node_exists):
        return
    # action
    node_exists[pos] = True
    # recursive descent
    traverse_and_mark(start_node.left, node_exists, pos * 2 + 1)
    traverse_and_mark(start_node.right, node_exists, pos * 2 + 2)
Finally, you need to check if there is a position in the list that is not occupied by True. In this case, you detect that the tree is not complete. This is implemented as follows:
def all_assigned(node_exists):
    for exists in node_exists:
        if not exists:
            return False
    return True
If you remember the built-in function all() you can shorten the implementation—I keep the helper function because it communicates the algorithm more clearly.
def all_assigned(node_exists):
    return all(node_exists)

Phew, that was quite a bit of work so far, and you needed several tricks. On a positive note, this algorithm works. I’ll show that later along with the algorithm converted purely to recursive processing based on these ideas.

On the negative side, however, you need quite a bit of additional memory depending on the tree’s size. Let’s see how you can avoid this by using the purely recursive variant.

Recursive algorithm The goal is to eliminate the use of the list and work only recursively. Therefore, the previously created traverse_and_mark() function is a good starting point. Since you’re not allowed to use a list as a data store, you need the number of nodes as a parameter.
def is_complete_rec(start_node):
    return __is_complete_rec_helper(start_node, 0, count_nodes(start_node))
def __is_complete_rec_helper(start_node, pos, node_count):
    if start_node is None:
        return True
    if pos >= node_count:
        return False
    if not __is_complete_rec_helper(start_node.left, 2 * pos + 1, node_count):
         return False
    if not __is_complete_rec_helper(start_node.right, 2 * pos + 2, node_count):
         return False
    return True

Without the intermediate steps, it would have been challenging—at least for me—to formulate the task recursively since the trick of the logic in the position calculation can hardly be derived without the list in mind. It is quite impressive what these few lines accomplish.

Verification

Again, you construct the tree and modify it after testing. If you take away the node H or I individually or both, then completeness is no longer given.
def main():
    F = create_completness_example_tree()
    TreeUtils.nice_print(F)
    print("is_complete?", is_complete(F))
    print("is_complete_rec?", is_complete_rec(F))
    # modification: remove leaves under H
    H = F.right
    H.left = None
    H.right = None
    TreeUtils.nice_print(F)
    print("is_complete?", is_complete(F))
    print("is_complete_rec?", is_complete_rec(F))
def create_completness_example_tree():
    F = BinaryTreeNode("F")
    TreeUtils.insert(F, "D")
    TreeUtils.insert(F, "H")
    TreeUtils.insert(F, "B")
    TreeUtils.insert(F, "E")
    TreeUtils.insert(F, "A")
    TreeUtils.insert(F, "C")
    TreeUtils.insert(F, "G")
    TreeUtils.insert(F, "I")
    return F
If you run this main() function, you get the expected results—moreover, they are consistent for the function variations:
                         F
             |-----------+-----------|
             D                       H
       |-----+-----|           |-----+-----|
       B           E           G           I
    |--+--|
    A     C
is_complete? True
is_complete_rec? True
                       F
           |-----------+-----------|
           D                       H
     |-----+-----|
     B           E
  |--+--|
  A     C
is_complete? False
is_complete_rec? False

8.3.13 Solution 13: Tree Printer (★★★★★)

In this exercise, you implement a binary tree’s graphical output, as you have seen before in the examples. Therefore, you initially solve the basics in the first three parts of the assignment and then proceed to the trickier graphical presentation of trees.

Tip

Use a fixed grid of blocks of width three. This significantly contributes to a balanced representation and reduces complexity.

Example

The following tree should cover various special cases:
                      F
          |-----------+-----------|
          D                       H
    |-----+                       +-----|
    B                                   I
 |--+--|
 A     C

Solution 13a: Width of a Subtree (★★✩✩✩)

In this part of the exercise, you are asked to find the maximum width of a subtree of a given height using the function subtree_width(height). For simplicity, you assume that a maximum of three characters represents the nodes. Besides, there is a distance of at least three characters between them. This is true for the leaves when the tree is full. On higher levels, there is naturally more space between the nodes of two subtrees.

Examples

Examples On the left, you see a tree of height 2, and on the right, a tree of height 3. Based on the grid of three, you get 9 and 21 as widths. See Figure 8-13.

Height

Total width

Width of subtree

1

3

0 (no subtree existing)

2

9

3

3

21

9

4

45

21

Figure 8-13

Tree width

Algorithm In the diagram, you recognize that the lowest level of a binary tree can contain at most 2n nodes, with n as the height of the tree. In order not to exceed the scope you want to ignore variable widths of the nodes. To determine the maximum width for a height, the total width is as follows:

max_num_of _leaves ∗ leaf _width + (max_num_of _leaves − 1) ∗ spacing

This is the basis for the following implementation. Perhaps the last computation is a bit tricky. You have to subtract the spacing and divide by two since you only want to determine the maximum width of a subtree.
def subtree_width(height):
    if height <= 0:
        return 0
    leaf_width = 3
    spacing = 3
    max_num_of_leaves = pow(2, height - 1)
    width_of_tree = max_num_of_leaves * leaf_width +
                    (max_num_of_leaves - 1) * spacing
    width_of_subtree = (width_of_tree - spacing) // 2
    return width_of_subtree

Solution 13b: Draw Node (★★✩✩✩)

Write function draw_node(current_node, line_length) that creates a graphical output of a node, generating the given set of spaces appropriately. The node value should have a maximum of three characters and be placed in the middle.

Tip

Remember that if the current node has a left successor, the representation of the layer below starts on the left with the string ‘ |-’.

Example

The example shows a single node with a spacing of five characters. Besides, the node value is center-aligned in a three-character box. See Figure 8-14.
Figure 8-14

Dimensions when drawing nodes

Algorithm As usual, it is a good idea to reduce the complexity by subdividing an assignment into several smaller subtasks. Using function spacing() you create the required spacing both to the left and right of the node representation. Its preparation first checks for the special cases of no existence or no value in the node. Then this corresponds graphically to a free space of three characters. Otherwise, you pad the value converted to a string with spaces if it is shorter than three characters. If it is longer, you truncate the text to three characters. This is done in the function stringify_node_value(node). Because subsequent lines start with the text ‘|-’ if a left successor exists, you add three more spaces to the front of your string representation.
def draw_node(current_node, line_length):
    str_node = " "
    str_node += spacing(line_length)
    str_node += stringify_node_value(current_node)
    str_node += spacing(line_length)
    return str_node
def stringify_node_value(node):
    if node is None:
        return " "
    if node.item is None:
        return " "
    node_value = str(node.item)
    if len(node_value) == 1:
        return " " + node_value + " "
    if len(node_value) == 2:
        return node_value + " "
    return node_value[0:3]
def spacing(line_length):
    return " " * line_length

Solution 13c: Draw Connection Lines (★★✩✩✩)

Write function draw_connections(node, line_length) to build a graphical output of the connection lines of a node to its two successors. Missing successors must be handled correctly.

Tip

The line length refers to the characters between the node representations. The parts representing ends are still to be appended appropriately in each case, as well as the middle connector.

Example

The following figure visualizes all cases relevant in drawing, with none, one, and two successor(s).
                        F
            |-----------+-----------|
            D                       H
      |-----+                       +-----|
      B                                   I
   |--+--|
   A     C
A schematic representation is shown again in Figure 8-15.
Figure 8-15

Schematic representation of the connecting lines

Algorithm When drawing the connecting lines below a node, all three variants with and without left or right successor are to be covered. Even a little more interesting is the fact that a non-existent node must also produce a corresponding output of blanks. This is needed if there are no children on the left side. Otherwise, the nodes on the right side would not be indented correctly.

You subdivide the drawing into three parts. First, you prepare the left part of the output with draw_left_connection_part(). After that, in draw_junction(node) you create the connection point respecting all special cases. Finally, with draw_right_connection_part() you prepare the right part.
def draw_connections(node, line_length):
    if node is None:
        return " " + spacing(line_length) +
                " " + spacing(line_length) + " "
    connection = draw_left_connection_part(node, line_length)
    connection += draw_junction(node)
    connection += draw_right_connection_part(node, line_length)
    return connection
def draw_left_connection_part(node, line_length):
    if node.left is None:
        return " " + spacing(line_length)
    else:
        return " |-" + draw_line(line_length)
def draw_right_connection_part(node, line_length):
    if node.right is None:
        return spacing(line_length) + " "
    else:
        return draw_line(line_length) + "-| "
def draw_junction(node):
    if node.left is None and node.right is None:
        return " "
    elif node.left is None:
        return " +-"
    elif node.right is None:
        return "-+ "
    else:
        return "-+-"
def draw_line(line_length):
    return "-" * line_length

Solution 13d: Tree Representation (★★★★★)

Combine all solutions of the parts of the exercise and complete the necessary steps to be able to print an arbitrary binary tree suitably on the console. To do this, write function nice_print(node).

Example

The output of the tree shown in the introductory example should also look something like this through nice_print():
                       F
           |-----------+-----------|
           D                       H
     |-----+                       +-----|
     B                                   I
  |--+--|
  A     C
Also, check your algorithm with a real monster of a tree, which you can find in the sources. Here is a much-slimmed-down representative:
                                  BIG
           |-----------------------+-----------------------|
           b2                                             f6
|-----------+-----------|                     |-----------+-----------|
a1                     d4                    d4                      g7
                 |-----+-----|          |-----+-----|
                c3          f6         b2          e5
                          |--+--|   |--+--|
                         e5    g7  a1    c3

Algorithm In the previous task, you learned how to map binary trees to lists or arrays. Here, this has to be slightly modified because in the tree nodes can be missing at arbitrary places in contrast to completeness. For computing the size of the list, you need the height of the tree. This is also important for computing the corresponding distances and line lengths. In this case, the trick also helps determine the maximum width of a subtree and use it appropriately.

These ideas mentioned earlier may be picked up to create a suitable list in which the nodes are stored in a scattered manner. The following function will assist you in doing so:
def fill_nodes_into_list(start_node):
    height = get_height(start_node)
    nodes = [None] * pow(2, height)
    traverse_and_mark(start_node, nodes, 0)
    return nodes
def traverse_and_mark(start_node, nodes, pos):
    if start_node is None:
        return
    if pos >= len(nodes):
        return
    # action
    nodes[pos] = start_node
    # recursive descent
    traverse_and_mark(start_node.left, nodes, pos * 2 + 1)
    traverse_and_mark(start_node.right, nodes, pos * 2 + 2)

For drawing, the tree and the list are traversed level by level and the graphical representation is prepared. However, this has the disadvantage that very extensive trees also require quite a lot of additional memory when drawing since they are kept as an array or list.

There are still a few challenges waiting for you:

  • As you start drawing at the top, you need to move the previously prepared lines for each new level by appropriate positions to the right.

  • The distances between the nodes and the lengths of the connecting lines have to be computed and kept depending on the total height, the current level, and position. Thereby the lowest level still needs special treatment.

Figure 8-16 illustrates the grid and the different distances between the nodes per level and from one level to the next.
Figure 8-16

Spacing between nodes

The associated implementation benefits from the use of the helper functions:
def nice_print_v1(node):
    if node is None:
        return
    tree_height = get_height(node)
    all_nodes = fill_nodes_into_list(node)
    # traverse level by level
    offset = 0
    lines = []
    for level in range(tree_height):
        line_length = subtree_width(tree_height - 1 - level)
        # indent predecessor lines to the right
        for i in range(len(lines)):
             lines[i] = " " + spacing(line_length) + lines[i]
        nodes_per_level = pow(2, level)
        node_line = ""
        connection_line = ""
        for pos in range(nodes_per_level):
            current_node = all_nodes[offset + pos]
            node_line += draw_node(current_node, line_length)
            node_line += spacing_between_nodes(tree_height, level)
            connection_line += draw_connections(current_node, line_length)
            connection_line += spacing_between_connections(tree_height, level)
        lines.append(node_line)
        lines.append(connection_line)
        # jump forward in the list
        offset += nodes_per_level
    for line in lines:
        print(line)
def spacing_between_nodes(tree_height, level):
    spacing_length = subtree_width(tree_height - level)
    spacing = " " * spacing_length
    if spacing_length > 0:
        spacing += " "
    return spacing
def spacing_between_connections(tree_height, level):
    spacing_length = subtree_width(tree_height - level)
    return " " * spacing_length

Memory-optimized algorithm In the following, I would like to present a modification that does not need any additional memory. Instead, it renders the graphical representation of the tree with a level order traversal. You use a list with single lines, wherein those with nodes and connecting lines alternate. In my opinion, the previously shown version is somewhat clearer. The following version needs the special treatment of changing levels, which is performed more naturally in the first version.

Overall, however, it is still a clear level order traversal, whose action is a bit more extensive in this case.
def nice_print(start_node):
    if start_node is None:
        return
    to_process = Queue()
    # very cool: tuple (node, level)
    to_process.enqueue((start_node, 0))
    tree_height = get_height(start_node)
    lines = []
    level = 0
    node_line = ""
    connection_line = ""
    additional_left_spacing = ""
    while not to_process.is_empty() and level < tree_height:
        # levelorder
        current_node_and_level = to_process.dequeue()
        current_node = current_node_and_level[0]
        node_level = current_node_and_level[1]
        line_length = subtree_width(tree_height - 1 - level)
        # change in level
        if level != node_level:
            level = node_level
            line_length = subtree_width(tree_height - 1 - level)
            lines.append(node_line)
            lines.append(connection_line)
            for i in range(len(lines)):
                 lines[i] = " " + additional_left_spacing +
                            spacing(line_length) + lines[i]
            node_line = ""
            connection_line = ""
        node_line += draw_node(current_node, line_length)
        node_line += spacing_between_nodes(tree_height, level)
        connection_line += draw_connections(current_node, line_length)
        connection_line += spacing_between_connections(tree_height, level)
        # levelorder
        if current_node is not None:
            to_process.enqueue((current_node.left, level + 1))
            to_process.enqueue((current_node.right, level + 1))
        else:
            # artificial placeholders
            to_process.enqueue((None, level + 1))
            to_process.enqueue((None, level + 1))
    for line in lines:
        print(line)

Verification

You have developed quite a bit. Now you want to see the fruits of your labor. For this purpose, you use the trees from the introductory example. The first tree shows well the principle way of working. The second is a combination of the previous example trees, but rotated to the left and right and united under a new root with the value BIG.
def create_tree_print_example_tree():
    F = BinaryTreeNode("F")
    TreeUtils.insert(F, "D")
    TreeUtils.insert(F, "H")
    TreeUtils.insert(F, "B")
    TreeUtils.insert(F, "A")
    TreeUtils.insert(F, "C")
    TreeUtils.insert(F, "I")
    return F
def create_big_tree():
    d4a = example_trees.create_example_tree()
    d4b = example_trees.create_example_tree()
    BIG = BinaryTreeNode("BIG")
    BIG.left = rotate_right(d4a)
    BIG.right = rotate_left(d4b)
    return BIG
These functions result in the following trees:
                      F
          |-----------+-----------|
          D                       H
    |-----+                       +-----|
    B                                   I
 |--+--|
 A     C
                                     BIG
              |-----------------------+-----------------------|
             b2                                              f6
  |-----------+-----------|                       |-----------+-----------|
 a1                      d4                      d4                      g7
                   |-----+-----|            |-----+-----|
                  c3          f6           b2          e5
                            |--+--|      |--+--|
                           e5    g7     a1    c3
If you want to see how beautifully really expansive trees are rendered, call the function for the following construct:
def create_monster_tree():
    mon = BinaryTreeNode("MON")
    mon.left = create_big_tree()
    mon.right = create_big_tree()
    return mon

In the companion project, you will find a double combination of this monster tree, which for fun I have named King Kong.

8.4 Summary: What You Learned

This chapter covered probably the most complex topic in this book, which is binary trees. As in many other languages, they are not part of standard Python. However, binary trees are suitable for solving numerous problems elegantly. Therefore, this chapter gave an introduction. Besides things like rotation, even mathematical calculations, for example, can be represented and processed very smartly using binary trees. Something challenging and to puzzle over was certainly the check for completeness and the graphical output of a binary tree.

In the next chapter, you continue with searching and sorting, which are essential topics in computer science like binary trees.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset