Version 2 (modified by inerte@…, 13 years ago) (diff)

typos and clarification

There's a good article explaining what's Modified Preorder Tree Traversal on SitePoint. I am not going to explain the whole theory here, just offer some code so you can implement it quickly.

Basically, it allows you to discover every children, or parent, or the whole tree, with a single query. Very efficient! And good for threaded discussions...

I modified these snippets from an app I coded in the portuguese language, with more features than what's pasted here. If there's anything wrong, send me an email, because I do have it working :)

Here's a model, a view and a couple functions to help you implement it.


What you really need are the lft and rght "columns". Yes, they mean left and right, but these are reserved SQL words. Everything else is optional. You will probably want an "article" or "post" fields, using ForeignKey, to say where the comment belongs to. If you do add something like this, don't forget to change the SQL queries to add the column.

class Comment(meta.Model):
    body = meta.TextField()
    lft = meta.PositiveIntegerField(db_index = True)
    rght = meta.PositiveIntegerField(db_index = True)

New record

I have this on my request (form) processing view, but you can put it anywhere (_pre_save() it's a good idea). The comment_id pk is the comment we're replying to, the one that will become the parent:

comment = get_object_or_404(comments, pk = comment_id)

target_rght = comment.rght - 1

new_comment_lft = target_rght + 1
new_comment_rght = target_rght + 2
cursor = db.cursor()   

cursor.execute("UPDATE `app_comments` " \
               "SET `rght` = `rght` + 2 " \
               "WHERE `rght` > %i" % int(target_rght))

cursor.execute("UPDATE `app_comments` " \
               "SET `lft` = `lft` + 2 " \
               "WHERE `lft` > %i" % int(target_rght))


new_comment = comments.Comment(body = some_var
                              lft = new_comment_lft,
                              rght = new_comment_rght,

Getting the tree

comment_list = comments.get_list(order_by=['lft'])

stack = []
for comment in comment_list:
    # [:] creates a copy of the list, needed because .pop() modifies it on each iteration and mess with the loop
    stack_copy = stack[:]
    for j in stack_copy:
        if j < comment.rght:

    stack_size = len(stack)

    comment.stack = stack_size


So, what have we done? There's a "stack" attribute on each comment now that tells you "how far" each comment is from another. For example, every "root" comment (the direct reply to a "post", for example) has a stack of 1. Every comment that's an answer to the root comments has a stack of 2. The stack respects the order (because of order_by=lft?) that the comments were inserted at the database. So we end up with comments having stacks numbered like this:



If you want to show the comments a little far from the left viewport border, based on their stack numbers, use this on your template:

<div style="margin-left:{% widthratio comentario.stack 20 100 %}%">
  {{ comment.body }}

The same can be done but shrinking a table. It gets smaller, aligned to the right, the further the comment is stacked:

<table style="width:{% widthratio comentario.stack 500 100 %}%" align="right">
  {{ comment.body }}
Back to Top