Title: Recursively draw binary trees in Python

[A binary tree drawn in Python]

A binary tree is a structure made up of branches and nodes (the places where the branches meet). At each node, the current branch either ends or it splits into two new branches, hence the name "binary."

This example shows how you can draw a binary tree recursively, but before I get to that, I'll briefly explain the tree's parameters.

For more information about recursion, trees, and other interesting algorithms, see my book Essential Algorithms: A Practical Approach to Computer Algorithms Using Python and C#.

Parameters

If you look at the picture at this top of this post, you'll see that the program has four parameters:

depth—Indicates how many times the branches branch before they end. Many recursive programs draw the simplest possible shape for depth 0, so the actual number of branches is one more than the depth. In this program the simplest "tree" is a single branch. If you start at the root at the bottom of the tree and follow all left branches, you'll see that the depth 10 tree has 11 levels of branches.
delta—When a branch splits, the two new branches point in the direction of the original branch plus or minus delta degrees.
length—This is the length of the current branch in pixels.
scale—When a branch splits, the two child branches have lengths equal to the original branch's length multiplied by the scale value.

[How delta, length, and scale affect a branch in a binary tree]

The picture on the right shows how the delta, length, and scale values affect a branching.
You can get some interesting results by changing the tree parameters. The following pictures show a few examples. [A binary tree with modified depth, delta, length, and scale parameters]

[A binary tree with modified depth, delta, length, and scale parameters]

Generating Trees

The key to the program is the following remarkably simple get_binary_tree function. In fact, this code is so simple that it's significantly shorter than the explanation that follows.

def get_binary_tree(depth, delta, length, scale, x, y, angle=-math.pi/2, segments=None): '''Return a list of segments that draw a binary tree.''' if segments is None: segments = [] # Draw our segment. x1 = x + length * math.cos(angle) y1 = y + length * math.sin(angle) segments.append(((x, y), (x1, y1))) # If depth > 0, recurse. if depth > 0: get_binary_tree(depth - 1, delta, length * scale, scale, x1, y1, angle - delta, segments) get_binary_tree(depth - 1, delta, length * scale, scale, x1, y1, angle + delta, segments) # Return the segments list. return segments

The previous section described the function's first four parameters. The x and y parameters give the location of the tree's root.

The angle parameter gives the direction of the first branch (the trunk, if you will). This value defaults to -math.pi/2 so, if you omit it, the tree's trunk points upward.

The final parameter, segments, is an optional list of segments that already belong to the tree. When the main program calls this function, it doesn't have any segments yet, so this parameter defaults to None.

The function first creates checks the segments parameter. If this list is None, the code sets it equal to an empty list.

Next, the function creates one branch. The first end point is passed in via the x and y parameters. To find the second end point, the code takes the sine and cosine of the current branch's angle, multiplies it by the branch's length, and adds the result to x and y. That puts (x1, y1) at the point distance length away from (x, y) in the direction of angle.

Note that the sine and cosine functions expect their angle parameters to be in radians so the code is using radians at this point.

After it finds the second end point, the code appends a tuple holding the two end points to the segments list.

Next, if the function's depth parameter is greater than zero, the function calls itself recursively to draw the pair of branches leaving the current branch. (In case you don't know, recursion is the process of a function calling itself.) In the recursive calls, the code sets:

The depth parameter to one less than its current value
The original delta value because it doesn't change--every child branch makes the same angle with its parent branch
The length parameter equal to the current length parameter multiplied by scale
The original scale parameter because that does change either
The coordinates x1 and y1 because the child branches start where the parent branch ends
The child branches' angles, which are the current angle plus or minus delta
The segments list

Notice that the depth value passed into the recursive calls is one less than the current depth value. That's important because it ensures that the recursive calls will eventually stop and the function won't keep calling itself forever.

Each recursive call adds its branch to the segments list and possibly calls itself recursively again to make smaller and smaller branches.

When the recursive calls finish, the function returns its segments list.

Drawing Trees

The following draw method displays a binary tree.

def draw(self): '''Draw the tree.''' # Clear the canvas. self.canvas.delete(tk.ALL) # Get the drawing area coordinates. tk.Tk.update(self.canvas) canvas_wid = self.canvas.winfo_width() canvas_hgt = self.canvas.winfo_height() # Get the tree's parameters. depth = int(self.depth_entry.get()) delta = math.radians(float(self.delta_entry.get())) length = float(self.length_entry.get()) scale = float(self.scale_entry.get()) x = canvas_wid / 2 y = canvas_hgt * 0.95 # Generate the tree segments. segments = get_binary_tree(depth, delta, length, scale, x, y) # Draw the segments. for segment in segments: self.canvas.create_line(segment[0], segment[1], fill='red')

This code first clears the program's Canvas widget and gets its current size. It then gets the parameters that you entered on the window and sets x and y to a point near the middle bottom of the canvas.

The program then calls get_binary_tree to get the segments that make up the binary tree. It finishes by looping through the returned segments drawing each on the canvas.

That's all there is to it!

Conclusion

The get_binary_tree function generates a binary tree's segments and the app's draw method draws those segments.

You can get some pretty interesting results by using different tree parameters. You can get other interesting results if you let left and right branches use different delta values. Other ideas for changes include drawing branches of different depths in different colors, randomizing the scale and delta values slightly at each branch, and changing the thickness of the segments at different depths.

Download the example to experiment with it and to see additional details.

For more information about recursion, trees, and other interesting algorithms, see my book Essential Algorithms: A Practical Approach to Computer Algorithms Using Python and C#.