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 this , 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.

What do you mean by "left to right horizontally"? Do you mean you want to produce your graphic but rotated left 90 degrees? If so, why don't you use a graphics editor and show us a rotated diagram so we see just what you want? If you don't have such an editor, do you want us to do that for you? — Rory Daulton
– Rory Daulton, Commented Jun 14, 2017 at 0:53
Here! I tried my best with paint and it looks terrible but i think you should get the idea !here — eshanrh
– eshanrh, Commented Jun 14, 2017 at 1:31

cdlane · Accepted Answer · 2017-06-14 09:15:50Z

1

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.

answered Jun 14, 2017 at 9:15

cdlane

42.2k5 gold badges37 silver badges87 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

eshanrh Over a year ago

Wow! thats an awesome waaaaaay neater way to do it. What I don't understand and maybe what you could explain a little bit better, is the math in the middle of the code ` distance = (GENERATION_DISTANCE2 + (2d * DOT_DIAMETER / 2)**2)**0.5 angle = acos(GENERATION_DISTANCE / distance)

cdlane Over a year ago

@notcompletelyrational, this is one of those triangle calculations, "given I know the (fixed) distance to the next generation, and I know how wide my wide my next generation will be, what angle should I use to reach a node?" I'm not deft at geometry so there may be a simpler way to express this equation but the gist is the distance to each generation (column) is fixed so the angle must increase as the vertical space occupied by subgraphs increases.

user1620443 · Accepted Answer · 2017-06-14 01:26:00Z

1

As far as I can see:

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.
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.

edited Jun 14, 2017 at 1:26

answered Jun 14, 2017 at 1:14

user1620443

7943 silver badges14 bronze badges

3 Comments

eshanrh Over a year ago

Thanks so much! It looks like it does work! Also, why was 10*(2**d) used? was that just some arbitrary equation just to get smaller distances? or was there reasoning behind it? If so, what?

eshanrh Over a year ago

I understand the point of it, how it decreases the size of the forward command for each smaller depth, but I don't understand why that equation exactly was used

user1620443 Over a year ago

In general, on the last level N, you will have 2^N nodes. Assuming they are equally spaced by a vertical distance d(N), the 2^(N-1) nodes of the parent level, should be spaced by d(N-1) = 2*d(N) (You can try to draw to see it). Using that formula ensures that the spacing of each parent level is 2 times the spacing of the children one, while keeping the angles fixed. Of course, this is not the only way and you could decide to change angles to keep lengths fixed, or do some more exotic stuff.

Roni Lazimi · Accepted Answer · 2019-04-05 20:21:14Z

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

Process:

Draw the node being visited (midway through height bounds)
Calculate new bounds; the height of current node will become upper bound of the lower subtree, and the lower bound of the upper subtree
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)

Collectives™ on Stack Overflow

Python Turtle Recursive Binary Tree

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related