Python Turtle Recursive Binary Tree

Question

My goal is to draw, with the python turtle, a binary tree, in the sense that each line branches into 2, and each of those branches into another two, etc, going from left to right, looking like , except from left to right horizontally. Here's what i have until now, and it works, but if you run it you quickly realise that it's messed up in a lot of ways.

def tree(d,x1,y1):
   #d is the depth

   if d==0: #base case
       return 0

   a = t.Turtle()
   b = t.Turtle()

   t.penup()

   a.goto(x1,y1)
   b.goto(x1,y1) # move to the correct position

   t.pendown()

   a.left(30)
   b.right(30)
   a.forward(50)
   b.forward(50)

   ax,ay = a.pos() #get position of new turtles
   bx,by = b.pos()

   input() # Debug ( PRESS ENTER FOR EACH LOOP)
   tree(d-1,ax,ay)  #recurse top branch
   tree(d-1,bx,by)  #recurse bottom branch

tree(3,0,0)

Can someone tell me what's wrong and maybe how to fix it? I can tell the angles need to change, but I don't know what to.

Answer 1

One nice way to work out the solution involves passing height bounds as arguments to the recursive function

Process:

1. Draw the node being visited (midway through height bounds)
2. Calculate new bounds; the height of current node will become upper bound of the lower subtree, and the lower bound of the upper subtree
3. Call method on child nodes of current node, with new bounds

Example (brackets are bounds, and each node –O- maps to an actual recursive call):

[             O            ]
[      O     ][      O     ]
[  O  ][  O  ][  O  ][  O  ]

Here's a snippet of code from my solution (Find the entire program on my GitHub repo: BinaryTreeVisualization).

def draw_tree(bst, node_radius, root, bound_bottom, bound_top, x_pos, x_step):

    if (root is not None):

        # Drawing current subtree root
        root_y = (bound_bottom + bound_top) // 2
        draw_node(x_pos, root_y, node_radius)

        # Drawing bottom subtree (bottom: same, top: root_y)
        draw_tree(bst, node_radius, root.left, bound_bottom, root_y, x_pos + x_step, x_step)
        # Drawing top subtree (bottom: root_y, top: same)
        draw_tree(bst, node_radius, root.right, root_y, bound_top, x_pos + x_step, x_step)

    pass

def draw_node(x, y, radius=5):
    canvas.penup()
    canvas.goto(x, y)
    canvas.pendown()
    canvas.dot(radius * 2)
    pass

And here's an example image of a tree (using repo program)

Answer 2

My solution attempts to reproduce angles and relationships between nodes of the original example.

However, my primary motivation is that the OP's code, and currently accepted solution, both generate lots of turtles. This is an issue as turtles are maintained on a global list, and not garbage collected, so that creating them unnecessarily, wastes space. At depth 4, the algorithms shown so far would create 30 turtles that would be unwanted and inaccessible after tree() runs. My solution below allows you pass in a single turtle to use for drawing the entire graph:

from math import acos
from turtle import Turtle, Screen

DOT_DIAMETER = 20
GENERATION_DISTANCE = 75

def tree(turtle, d, origin):
    # d is the depth

    turtle.penup()
    turtle.setposition(origin)
    turtle.dot(DOT_DIAMETER)

    if d == 0:  # base case
        return

    distance = (GENERATION_DISTANCE**2 + (2**d * DOT_DIAMETER / 2)**2)**0.5
    angle = acos(GENERATION_DISTANCE / distance)

    turtle.pendown()
    turtle.left(angle)
    turtle.forward(distance)
    upper = turtle.position()
    turtle.right(angle)

    turtle.penup()
    turtle.setposition(origin)
    turtle.pendown()
    turtle.right(angle)
    turtle.forward(distance)
    lower = turtle.position()
    turtle.left(angle)

    tree(turtle, d - 1, upper)  # recurse upper branch
    tree(turtle, d - 1, lower)  # recurse lower branch

screen = Screen()

yertle = Turtle()
yertle.radians()  # to accommodate acos()

tree(yertle, 3, (-150, 0))

screen.mainloop()

OUTPUT:

You can call screen.turtles() after tree() to see the list of turtles that have been created.

Answer 3

As far as I can see:

1. You should call penup() and pendown() on the turtle instances a and b, not on the module. This will solve the visible lines on goto.

2. If you fix length and angle on each depth level, on the second level you will start having superimposed nodes. The vertical distance between two nodes on level n should be greater than the distance on level n+1, to be sure you don't have overlapping nodes (or edges) at lower levels. Note that the vertical distance of two nodes on level n+1 is 2*forward(n)*sin(angle(n)).

Something like

def tree(d,x1,y1):
   #d is the depth

   if d==0: #base case
       return 0

   a = t.Turtle()
   b = t.Turtle()

   a.penup()
   b.penup()

   a.goto(x1,y1)
   b.goto(x1,y1) # move to the correct position

   a.pendown()
   b.pendown()

   a.left(45)
   b.right(45)
   a.forward(10*(2**d)) 
   b.forward(10*(2**d))

   ax,ay = a.pos() #get position of new turtles
   bx,by = b.pos()

   tree(d-1,ax,ay)  #recurse top branch
   tree(d-1,bx,by)  #recurse bottom branch

should work.