Hello. I implemented an AVL Binary Tree with insertion based on left and right rotation (as is by default) and deletion with the same balance checking as the insertion.

I want to draw the tree in Win32 GDI and I succeded so far exept that I cant store the nodes depth level after an AVL rotation without iterating the whole tree again. I want to store nodes levels so I can draw the lines that connect each nodes at different angles for each level so the nodes wont touch.

As in picture http://s23.postimg.org/w454umihn/avl.jpg

When I draw the Tree I get every node by depth with a Queue that stores the children of a node and after that goes to the other and display the node and so on. I can store the level of the node in the Queue because I dont know when the level changes as the Queue always stores children but never knows when the level is finished. Or at least I dont know how to implement that.

Please give me a hint. Should I try storing the levels when the Queue is processed and the tree is traversed in depth or should I store the node of every level in a different traversal ?

Thanks

With your image, and description, are you asking about how to lay them out on the screen?

Assuming you are just talking about visual layout, I see two options. The first would be to dynamically size the rows based on how full they are. That is going to require a traversal. The other option is to layout the screen as though it were a full tree, then just leave those spaces blank.

I'll assume you go with the second option, to just lay out the tree as though it were full. That prevents any weird visual wiggling and shaking as the tree gets rebalanced, the spaces are just full or empty.

Since an AVL tree is always balanced, you can figure out the layouts you need based on the count of nodes in the tree. The height is easily calculated ( log2(n+1) ), and each row has an easily calculated number of nodes (2^level for zero-based levels).

Now that you know how many nodes are on a level and how many levels you've got, you can calculate the size of the boxes and the size of your viewport and figure out your needed layout accordingly.