# Traversals from the root in AVL trees and Red Black Trees

We all know that for insertion() operation in AVL tree following can happen:

We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance we have to check heights of the ancestors of the newly inserted node and in doing so, we could end up traversing up to the root.

I completely agree with this.

But according to me the same can happen in Red Black tree because first we would traverse down the tree to appropriate node and then insert the key.Then there is a possibility that a series of rotation and flip color operations could make us traverse the path up to the root.

Now my question is : why following statement is right?

In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node.

It came as a question, which of the following statements is right about AVL and Red Black trees and the option with given statement was marked correct in the answer key. I am trying to figure out mistake in my second observation?

• Can you give a citation for this claim? I just checked CLRS; in their implementation, the insert routine indeed only decendes, but then it calls fixup which restores all RB-properties, and that one moves up to the root again. There may be other implementations, though. Which one does your source use? – Raphael Jun 25 '15 at 8:46