“The main advantage of threaded trees is the reduction in traversal time and space.. Tree traversal is really time consuming + stack space consuming. We can reduce that, if we have threaded the tree with the empty nodes at the bottom.”
Before diving into the concept behind this, understand and re-study the following links,
In this article, we will just see how to thread the tree so that, all the leaf nodes get connected to its in-order successor nodes. As its a successor node, we connect the right nodes to the appropriate root.
The important property of the in-order successor node is that,
- If the node you see has a NULL right node and the node is present as left child for its parent, simply connect the NULL node to the parent.
- If the node you see has a NULL right node but its a right child for its parent, then move to a parent for which our node is not the right!!
This is already discussed clearly in successor and predecessor. But how to do this with recursion and without a parent node part of the tree!!
Little bit tricky!!.. :) But if you understand that, you need to create cycles with the current parent. you will catch the way!!
Consider you have a tree like this,
Firstly, you need to do recursion so that child gets connected to parent. That is,
7->3, 8->3, 3->1,9->4, 4->1.. etc.
After you get this recursion, connect 7->right to 3 and 8->right also to 3. But when you need to connect 3 to 1, you just check whether traversing 3->right->right gives again the 3.. :)
7 8 –> right node connected to 3.
Between 3 and 8 there is a cycle, just detect this cycle and move the 8-th right node to the parent of 3. which is 1. :)
The above is what we need to achieve to get the in-order successor.
- we need to iterate until we find the right!!.. That’s why we need that for loop.
- we don’t use any extra space in this algorithm. We reuse the NULL nodes in the tree.
- We don’t have any difference between threaded node and normal node. :) We can traverse as usual.