Trees->Threaded Binary Tree->Concepts
|A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor. By doing this threading we avoid the recursive method of traversing a Tree, which makes use of stacks and consumes a lot of memory and time. |
The node structure for a threaded binary tree varies a bit and its like this --
Let's make the Threaded Binary tree out of a normal binary tree...
The INORDER traversal for the above tree is -- D B A E C. So, the respective Threaded Binary tree will be --
B has no right child and its inorder successor is A and so a thread has been made in between them. Similarly, for D and E. C has no right child but it has no inorder successor even, so it has a hanging thread. Clear!
|Index || Doubts / Clarifications || Related Topics || Web Links|