6.6 Threaded (Stack or Queue less) Binary Tree Traversals
In the previous sections, we have seen that the preorder, inorder, and postorder binary tree traversal used stack and the level order traversal traversal used the queue as the backend data structure. In this section, we will discuss new traversal algorithms that do not need both stacks and queues. Such traversal algorithms are called threaded binary tree traversals or stack/queue less traversals.
Problems with normal binary tree traversal
- Storage space required for large stacks and queues.
- The majority of pointers in any binary tree are NULL. For example, a binary tree with n nodes had n + 1 NULL pointers and they were wasted.
- It is very difficult to find the next node (preorder, inorder and postorder) for a given node.
Successor/Predecessor concept in binary tree
The section about Successor (Successor) and Predecessor (Predecessor) in the book is not mentioned by the author, so I have a reference here and here, we need to understand what it is before moving on.
Example with Inorder Successor in binary tree.
In a Binary Tree, the Inorder successor of a node is the next node in the Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in the Inorder traversal. Similar concept for Inorder Predecessor
Motivation for Threaded Binary Trees
To solve these problems, one idea is to store some useful information in NULL pointers (Leaf nodes pointing to left and right nodes are null, we’ll make use of them). If we look closely at the previous traversals, then a stack/queue is required because we have to record the current position to move to the right subtree after processing the left subtree. If we store useful information in NULL pointers, then we don’t have to store it in the stack/queue.
Binary trees that store such information in NULL pointers are called stream binary trees. From the discussion above, suppose that we want to store some useful information in NULL pointers. The next question is to store what?
The common convention is to put the predecessor/successor (predecessor/successor) information. That means, if we are dealing with preorder traversals, then for a given node, NULL left pointer will contain preorder predecessor information and NULL right pointer will contain preorder successor information. information).
These special pointers are called threads .
Classification Threaded Binary Trees
The classification is based on whether we are storing useful information in both NULL pointers or in just one of them.
- If we only store predecessor information in NULL left pointers, then we call those binary trees left threaded binary trees.
- If we only store succession information in NULL right pointers then we call those binary trees right threaded binary trees.
- If we store predecessor information in NULL left pointers and store successor information in NULL right pointers, then we call that binary tree fully threaded binary trees or simply threaded binary trees.
Note: For the rest of the discussion, we will only consider fully threaded binary trees.
Types of Threaded Binary Trees
Based on the discussion above, we see three representations for streamed binary trees.
- Preorder Threaded Binary Trees: NULL left pointer contains PreOrder’s predecessor information and NULL right pointer contains PreOrder’s successor information.
- Inorder Threaded Binary Trees: NULL left pointer contains Inorder’s predecessor information and NULL right pointer contains Inorder’s successor information.
- Postorder Threaded Binary Trees: NULL left pointer contains Postorder predecessor information and NULL right pointer contains Postorder successor information.
Note: Since the representations are similar, for the rest of the discussion we will use the InOrderthreaded binary tree.
Structure of Threaded Binary Tree
Any program that examines the tree must be able to distinguish between a regular left/right pointer and a thread . To do this, we use two additional fields in each node, giving us, for a threading tree, nodes of the following form:
Difference between binary tree structure and streamed binary tree
| Regular binary tree | Streamed binary tree | |
|---|---|---|
| If LTag == 0 | NULL | The left pointer will point to the in-order predecessor |
| If LTag == 1 | The left pointer will point to the left child node | The left pointer will point to the left child node |
| If RTag == 0 | NULL | The right pointer will point to the next in-order |
| If RTag == 1 | The right pointer will point to the right child node | The right pointer will point to the right child node |
Note: We can also define the same preorder/postorder difference.
For example, let’s try to represent a tree in inorder threaded form. The tree below shows what the inorder streamed binary tree should look like. Dotted arrows indicate threads. If we observe, the left pointer of the leftmost node (2) and the right pointer of the rightmost node (31) are hanging (pointing nowhere).
What should the leftmost and rightmost pointers point to?
In the representation of a streamed binary tree, it is convenient to use a special Dummy dummy node that always appears even for an empty tree. Note that the right tag of the Dummy node is 1 and its right child points to itself.
With this convention, the above tree can be represented as:
Find the Inorder Successor in the Inorder streamed binary tree
To find the inorder successor of a given node without using the stack, suppose that the node we want to find the inorder successor node is P. Strategy: If P has no right subtree, then return the right child of P. If P has a right subtree, then returns the left side of the nearest node whose left subtree contains P.
1 2 3 4 5 6 7 8 9 10 11 12 13 | public ThreadedBinaryTreeNode findInorderSuccessor(ThreadedBinaryTreeNode P){ ThreadedBinaryTreeNode Position; if(P.getRTag() == 0){ return P.getRight(); } else{ Position = P.getRight(); while(Position.getLtag() == 1){ Position = Position.getLeft(); } return Position; } } |
Time Complexity: O(n). Space Complexity: O(1).
Inorder Traversal in Inorder Threaded Binary Tree
We can start with the dummy dummy node and call InorderSuccessor() to access each node until we reach the dummy node.
1 2 3 4 5 6 7 8 | public void InorderTraversal(ThreadedBinaryTreeNode root){ ThreadedBinaryTreeNode P = findInorderSuccessor(root); while(P != root){ P = findInorderSuccessor(P); System.out.println(P.getData()); } } |
Time Complexity: O(n). Space Complexity: O(1).
Searching for PreOrder Successor in InOrder Threaded Binary Tree
Strategy: If P has a left subtree, return the left subtree of P. If P has no left subtree, return the right child node of the nearest node whose right subtree contains P.
1 2 3 4 5 6 7 8 9 10 11 12 13 | public ThreadedBinaryTreeNode findPreorderSuccessor(ThreadedBinaryTreeNode P){ ThreadedBinaryTreeNode Position; if(P.getLtag()){ return P.getLeft(); } else{ Position = P; while(Position.getRTag() == 0){ Position.getRight(); } return Position.getRight(); } } |
PreOrder Traversal of InOrder Threaded Binary Tree
As in inorder traversal, let’s start with dummy dummy node and call findPreorderSuccessor() to access each node until we get dummy node back.
1 2 3 4 5 6 7 8 | public void PreoderTraversal(ThreadedBinaryTreeNode root){ ThreadedBinaryTreeNode P = findPreorderSuccessor(root); while(P != root){ P = findPreorderSuccessor(P); System.out.println(P.getData()); } } |
Time Complexity: O(n). Space Complexity: O(1).
Note : From the discussion above, it is clear that finding an ordered successor and preordering inorder and preorder successor is easy with threaded binary trees. But finding postorder successor is very difficult if we don’t use stack.
Insert more nodes into InOrder Threaded Binary Trees
For the sake of simplicity, let’s assume that there are two nodes P and Q and we want to attach Q to the right of P. For this we will have two cases.
- node P has no right children: In this case, we simply attach Q to P and change its left and right pointers.
- node P has right child (say R): In this case, we need to traverse the left subtree of R and find the left most node, then update the left and right pointers of that node ( as shown below).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public void insertRightInInorderTBT(ThreadedBinaryTreeNode P, ThreadedBinaryTreeNode Q){ ThreadedBinaryTreeNode Temp; Q.setRight(P.getRight()); Q.setRTag(P.getRTag()); Q.setLeft(P); Q.setLtag(0); P.setRight(Q); P.setRTag(1); if(Q.getRTag() == 1){ //Case-2 Temp = Q.getRight(); while(Temp.getLtag() == 1){ Temp = Temp.getLeft(); } Temp.setLeft(Q); } } |
Time Complexity: O(n). Space Complexity: O(1).
This is a rather difficult and abstract article with the idea of using leaf nodes that are pointing to null in vain. You can refer to the following links: here and here