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.
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
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.
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
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
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
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.
Depth-First Searches
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.
The Properties Level and Height
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.
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:
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
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.
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
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
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.
Use a fixed grid of blocks of width three. This significantly contributes to a balanced representation and reduces complexity.
Example
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
Height | Total width | Width of subtree |
---|---|---|
1 | 3 | 0 (no subtree existing) |
2 | 9 | 3 |
3 | 21 | 9 |
4 | 45 | 21 |
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.
Remember that if the current node has a left successor, the representation of the layer below starts on the left with the string ‘ |-’.
Example
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.
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
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
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).
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
Verification
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
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.
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 |
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 |
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.
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 | [ ] |
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
Surprise Algorithm
While preorder was quite easy to design iteratively, it became a bit more difficult with inorder and even really tricky with postorder.
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
Verification
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
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.
Verification
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.
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.
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
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.
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
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
Level | Value(s) | Result |
---|---|---|
0 | 4 | 4 |
1 | 2, 6 | 8 |
2 | 1, 3, 5, 8 | 17 |
3 | 7, 9 | 16 |
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
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-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.
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
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
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
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
To call your function recursively, you need to find the corresponding value sequences for preorder. How do you do this?
Verification
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.
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
Verification
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
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.
Verification
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
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!
Verification
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
Verification
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.
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
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
Verification
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
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.
Verification
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.
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
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.
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.
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
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.
Use a fixed grid of blocks of width three. This significantly contributes to a balanced representation and reduces complexity.
Example
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
Height | Total width | Width of subtree |
---|---|---|
1 | 3 | 0 (no subtree existing) |
2 | 9 | 3 |
3 | 21 | 9 |
4 | 45 | 21 |
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
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.
Remember that if the current node has a left successor, the representation of the layer below starts on the left with the string ‘ |-’.
Example
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.
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
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.
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
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.
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.
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.
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.
Verification
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.