A threaded binary tree is a binary tree that allows for the traversal of the tree without using recursive function calls or a stack data structure. Instead, each node in the threaded binary tree contains a reference to its successor (the next node to be visited in an in-order traversal) or a special value indicating that the node has a thread to its successor.
This article will discuss the concept of preorder successors in a threaded binary tree. To understand the preorder successor, we first need to understand the preorder traversal of a binary tree.
- Preorder traversal is a method of visiting each node in a binary tree in a particular order. In preorder traversal, we first visit the root node, then recursively visit the left subtree, and finally recursively visit the right subtree. Preorder traversal can be implemented using recursive function calls or a stack data structure.
- Now, let's consider a threaded binary tree. In a threaded binary tree, each node may have a thread to its successor, the next node to be visited in an in-order traversal. This means we can traverse the entire tree without recursive function calls or a stack data structure.
- To find the preorder successor of a node in a threaded binary tree, we first need to understand the relationship between preorder and inorder traversal. In preorder traversal, we visit the root node first, then the left subtree, and then the right subtree. In inorder traversal, we visit the left subtree first, then the root node, and then the right subtree.
The preorder successor of a node in a threaded binary tree is the next node to be visited in the preorder traversal. To find the preorder successor of a node, we can use the threads in the tree to navigate to the next node in the preorder traversal.
Let's consider an example. Suppose we have the following threaded binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
In this tree, each node has a thread to its successor in the inorder traversal. Dashed lines in the diagram below represent the threads:
1
/ \
2 --> 3
/ \ / \
4-->5 6-->7
- To find the preorder successor of node 1, we first visit the root node, which is node 1. The preorder successor of node 1 is the next node to be visited in preorder traversal, which is node 2.
- To find the preorder successor of node 2, we first visit node 2, which is the root node of the left subtree. The preorder successor of node 2 is the next node to be visited in preorder traversal after visiting the left subtree of node 2, which is node 4.
- To find the preorder successor of node 3, we first visit node 3, which is the root node of the right subtree. The preorder successor of node 3 is the next node to be visited in preorder traversal after visiting the left and right subtrees of node 3, which is node 6.
- To find the preorder successor of node 4, we first visit node 4, a leaf node. The preorder successor of node 4 is the next node to be visited in preorder traversal after visiting the right subtree of node 2, which is node 5.
- To find the preorder successor of node 5, we first visit node 5, which is a leaf node. The preorder successor of node 5 is the next node to be visited in preorder traversal after visiting the parent node of the node.
ALGORITHM
Here's an algorithm to find the preorder successor of a node in a threaded binary tree:
- If the node has a thread to its successor, return the successor node.
- If the node has a right child, return the right child.
- If the node is the left child of its parent and the parent has a right child, return the right child of the parent.
- If the node is the left child of its parent and the parent does not have a right child, return the parent of the parent.
- If the node is the right child of its parent and the parent has a right child, return the leftmost node in the subtree rooted at the right child of the parent.
- If the node is the right child of its parent and the parent does not have a right child, return NULL.
The above algorithm examines the threads and children of the given node and determines the next node to be visited in the preorder traversal. If the node has a thread to its successor, we return the successor node. Otherwise, we examine the node's children and parent to determine the next node in the preorder traversal. If the node is the left child of its parent, we first check if the parent has a right child, in which case we return the right child. If the parent does not have a right child, we return the parent of the parent. If the node is the right child of its parent, we first check if the parent has a right child, in which case we return the leftmost node in the subtree rooted at the right child of the parent. If the parent does not have a right child, we return NULL.
IMPLEMENTATION
// Writing a C++ implementation to determine the preorder successor of an L present in the binary tree.#include <iostream>using namespace std;struct __nod {struct __nod *Lft, *Rt, *parent;int ky;};__nod* new__nod(int ky){__nod* tempo = new __nod;tempo->Lft = tempo->Rt = tempo->parent = NULL;tempo->ky = ky;return tempo;}__nod* preorderSuccessor(__nod* root, __nod* n){//If we have a left child, it will have a preorder successor.if (n->Lft)return n->Lft;// Else, if the left child is not present and the right child is present, it will be considered the preorder successor.if (n->Rt)return n->Rt;// In case, the left child doesn't exist, then we have to traverse up to parent pointers and to the point where we reach a node that is supposed to be the left child of its parent.__nod *curr = n, *parent = curr->parent;while (parent != NULL && parent->Rt == curr) {curr = curr->parent;parent = parent->parent;}// In case we have arrived at the root node, the allotted node will not have any preorder successor.if (parent == NULL)return NULL;return parent->Rt;}Writing the main code to test the above-mentioned functions.int main(){__nod* root = new__nod(20);root->parent = NULL;root->Lft = new__nod(10);root->Lft->parent = root;root->Lft->Lft = new__nod(4);root->Lft->Lft->parent = root->Lft;root->Lft->Rt = new__nod(18);root->Lft->Rt->parent = root->Lft;root->Rt = new__nod(26);root->Rt->parent = root;root->Rt->Lft = new__nod(24);root->Rt->Lft->parent = root->Rt;root->Rt->Rt = new__nod(27);root->Rt->Rt->parent = root->Rt;root->Lft->Rt->Lft = new__nod(14);root->Lft->Rt->Lft->parent = root->Lft->Rt;root->Lft->Rt->Lft->Lft = new__nod(13);root->Lft->Rt->Lft->Lft->parent = root->Lft->Rt->Lft;root->Lft->Rt->Lft->Rt = new__nod(15);root->Lft->Rt->Lft->Rt->parent = root->Lft->Rt->Lft;root->Lft->Rt->Rt = new__nod(19);root->Lft->Rt->Rt->parent = root->Lft->Rt;__nod* res = preorderSuccessor(root, root->Lft->Rt->Rt);if (res) {printf("Preorder successor of %d is %d\n",root->Lft->Rt->Rt->ky, res->ky);}else {printf("Preorder successor of %d is NULL\n",root->Lft->Rt->Rt->ky);}return 0;}Output:
Example 2)
// Writing a Java implementation to figure out the preorder successor of a node in the binary tree.class Solution{static class __nod{__nod Lft, Rt, parent;int ky;};static __nod new__nod(int ky){__nod tempo = new __nod();tempo.Lft = tempo.Rt = tempo.parent = null;tempo.ky = ky;return tempo;}static __nod preorderSuccessor(__nod root, __nod n){//If we have a left child, it will have a preorder successor.if (n.Lft != null)return n.Lft;// Else, if the left child is not present and the right child is present, it will be considered the preorder successor.if (n.Rt != null)return n.Rt;// In case the left child doesn't exist, then we have to traverse up to parent pointers and to the point where we reach a node that is supposed to be the left child of its parent.__nod curr = n, parent = curr.parent;while (parent != null && parent.Rt == curr){curr = curr.parent;parent = parent.parent;}// In case we have arrived at the root node, the allotted node will not have any preorder successor.if (parent == null)return null;return parent.Rt;}Writing the main code to test the functions mentioned above.public static void main(String args[]){__nod root = new__nod(20);root.parent = null;root.Lft = new__nod(10);root.Lft.parent = root;root.Lft.Lft = new__nod(4);root.Lft.Lft.parent = root.Lft;root.Lft.Rt = new__nod(18);root.Lft.Rt.parent = root.Lft;root.Rt = new__nod(26);root.Rt.parent = root;root.Rt.Lft = new__nod(24);root.Rt.Lft.parent = root.Rt;root.Rt.Rt = new__nod(27);root.Rt.Rt.parent = root.Rt;root.Lft.Rt.Lft = new__nod(14);root.Lft.Rt.Lft.parent = root.Lft.Rt;root.Lft.Rt.Lft.Lft = new__nod(13);root.Lft.Rt.Lft.Lft.parent = root.Lft.Rt.Lft;root.Lft.Rt.Lft.Rt = new__nod(15);root.Lft.Rt.Lft.Rt.parent = root.Lft.Rt.Lft;root.Lft.Rt.Rt = new__nod(19);root.Lft.Rt.Rt.parent = root.Lft.Rt;__nod res = preorderSuccessor(root, root.Lft.Rt.Rt);if (res != null){System.out.printf("Preorder successor of %d is %d\n",root.Lft.Rt.Rt.ky, res.ky);}else{System.out.printf("Preorder successor of %d is null\n",root.Lft.Rt.Rt.ky);}}}Output:
Example 3)
// Writing a C# implementation to figure out the preorder successor of a node in the binary tree.using System;class TPT{public class __nod{public __nod Lft, Rt, parent;public int ky;};static __nod new__nod(int ky){__nod tempo = new __nod();tempo.Lft = tempo.Rt = tempo.parent = null;tempo.ky = ky;return tempo;}static __nod preorderSuccessor(__nod root, __nod n){//If we have a left child, it will have a preorder successor.if (n.Lft != null)return n.Lft;// Else, if the left child is not present and the right child is present, it will be considered the preorder successor.if (n.Rt != null)return n.Rt;// In case the left child doesn't exist, then we have to traverse up to parent pointers and to the point where we reach a node that is supposed to be the left child of its parent.__nod curr = n, parent = curr.parent;while (parent != null && parent.Rt == curr){curr = curr.parent;parent = parent.parent;}// In case, we have arrived at the root node, then the allotted node will not have any preorder successor.if (parent == null)return null;return parent.Rt;}Writing the main code to test the above-mentioned functions. public static void Main(String []args){__nod root = new__nod(20);root.parent = null;root.Lft = new__nod(10);root.Lft.parent = root;root.Lft.Lft = new__nod(4);root.Lft.Lft.parent = root.Lft;root.Lft.Rt = new__nod(18);root.Lft.Rt.parent = root.Lft;root.Rt = new__nod(26);root.Rt.parent = root;root.Rt.Lft = new__nod(24);root.Rt.Lft.parent = root.Rt;root.Rt.Rt = new__nod(27);root.Rt.Rt.parent = root.Rt;root.Lft.Rt.Lft = new__nod(14);root.Lft.Rt.Lft.parent = root.Lft.Rt;root.Lft.Rt.Lft.Lft = new__nod(13);root.Lft.Rt.Lft.Lft.parent = root.Lft.Rt.Lft;root.Lft.Rt.Lft.Rt = new__nod(15);root.Lft.Rt.Lft.Rt.parent = root.Lft.Rt.Lft;root.Lft.Rt.Rt = new__nod(19);root.Lft.Rt.Rt.parent = root.Lft.Rt;__nod res = preorderSuccessor(root, root.Lft.Rt.Rt);if (res != null){Console.Write("Preorder successor of {0} is {1}\n",root.Lft.Rt.Rt.ky, res.ky);}else{Console.Write("Preorder successor of {0} is null\n",root.Lft.Rt.Rt.ky);}}}Output:
FAQs
How do you find the preorder successor in a binary tree? ›
The pre-Order successor of a node in a Binary Tree is the node next to the current node in the pre-order traversal of a binary tree. Therefore preorder successor for 20 will be 10, 23 will be 39, etc.
How the inorder successor can be found in a threaded binary tree? ›So the basic idea of a threaded binary tree is that for the nodes whose right pointer is null, we store the in-order successor of the node (if-exists), and for the nodes whose left pointer is null, we store the in-order predecessor of the node(if-exists).
What is pre order threaded binary tree? ›There are three methods to apply thread binary tree. Each method corresponds to a particular type of tree traversal: Preorder threading: on this, the threads are applied to the higher node containing the preorder traversal of the tree. Inorder threading: the threads are applied considering the inorder traversal.
What is Postorder successor of a node in binary search tree? ›Since the root is the last node in postorder traversal, its successor is NULL.
What is the in-order successor of 15 in the given binary search tree? ›The in-order sequence can be found following the chronology of Left-> Root-> Right. Finding the in-order traversal sequence, we get 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20. The element that comes after 15 is its successor. It can be seen that 15's successor is 17.
How to find the inorder preorder and postorder traversal of a binary tree? ›For Inorder, you traverse from the left subtree to the root then to the right subtree. For Preorder, you traverse from the root to the left subtree then to the right subtree. For Post order, you traverse from the left subtree to the right subtree then to the root.
How do you find the threaded binary tree? ›In one-way threaded binary trees, a thread will appear either in the right or left link field of a node. If it appears in the right link field of a node then it will point to the next node that will appear on performing in order traversal. Such trees are called Right threaded binary trees.
What is threaded binary tree with example? ›"A binary tree is threaded by making all right child pointers that would normally be null point to the in-order successor of the node (if it exists), and all left child pointers that would normally be null point to the in-order predecessor of the node."
What is inorder successor of a node in binary tree practice? ›The inorder successor of a node p is the node q that comes just after p in the binary tree's inorder traversal. Given the root node of a binary search tree and the node p , find the inorder successor of node p . If it does not exist, return null .
What is a predecessor in binary tree? ›What is an in-order predecessor in a binary search tree? The in-order predecessor of a node in a Binary Search Tree is the node that comes before our key node when we write the inorder traversal of the tree.
What node is the successor of node A? ›
node A: Is the root of the tree, so its successor is undefined.
What is successor and predecessor in binary tree? ›The successors of a node are called its children; the unique predecessor of a node is called its parent. If two nodes have the same parent, they are called brothers or siblings. In a binary tree the two children are called the left and right.
What is Preorder function in binary search tree? ›- Preorder = (Root, Left subtree, Right Subtree)
- Inorder = (Left subtree, Root, Right Subtree)
- Postorder = (Left Subtree, Right subtree, Root)
A node's predecessor in a BST is the greatest value present in its left subtree. If the left subtree doesn't exist, then the predecessor can be one of his ancestors. Similarly, a node's successor in a BST is the smallest value present in its right subtree.
What is a post-order successor? ›If the given node is the left child of the parent and the right child is NULL, then the parent is the postorder successor. If the given node is the left child of the parent and the right child of the parent is not NULL, then the postorder successor is the leftmost leaf node of the parent's right subtree.
How to convert preorder to postorder in binary tree? ›- Step 1 - Preorder can be represented as root -> left -> right and postOrder can be represented as left -> right -> root.
- Step 2 - A loop is used, and the last element of the left group is taken as the pivot element.
The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.
What is the preorder traversal sequence of a binary tree 30 20 10 15 25 23 39 35 42? ›30, 20, 10, 15, 25, 23, 39, 35, 42. So, the In-order traversal of the BST is: 10, 15, 20, 23, 25, 30, 35, 39, 42. Hence, the correct answer is "option 4".
What is the preorder traversal of a binary search tree 12 8 6 2 7 9 10 16 15 19 17 20? ›In pre- order first node is the root. Explanation: Pre-order traversal is 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Now, anything which is in the left of root in in-order traversal will come to the left of root and other comes to the right of root.
What is an example of a preorder traversal of a binary tree? ›Example of preorder traversal
print 30 and recursively traverse the left subtree. next node is 20. now 20 have subtree so print 20 and traverse to left subtree of 20 . next node is 15 and 15 have subtree so print 15 and traverse to left subtree of 15.
How do I find my pre-order from Postorder traversal? ›
In the postorder traversal, all elements before the root node are of left subtree and after the root are of right subtree. Like this, we will find all elements and store the nodes in the stack and the print elements of the stack which gives the preorder traversal.
How do I get a preorder from Postorder? ›Pre-order = outputting the values of a binary tree in the order of the current node, then the left subtree, then the right subtree. Post-order = outputting the values of a binary tree in the order of the left subtree, then the right subtree, the the current node.
Which tree traversal is used in a threaded binary tree? ›Explanation: In threaded binary trees, the null left pointer points to the predecessor and the right null pointer point to the successor. In threaded binary trees, we can use in-order, preorder and postorder traversals to visit every node in the tree.
What is the difference between binary tree and threaded binary tree? ›In fact, a binary search tree is a concept that has nothing inherently to do with how the tree is implemented, while a threaded tree is only about how trees are implemented--i.e. how you set up the pointers in the tree nodes. A binary search tree can be a threaded tree if you decide to implement it that way.
What is the insertion of an element in a threaded binary tree? ›The insertion technique is similar to that of a binary search tree. The only difference is that the threaded binary tree has to take into account the threads updates. The new node value becomes the root node, and both the left and right pointers of the value will be set to NULL.
What are the steps to perform in order traversal on threaded binary tree? ›- We go to the left most node 1.
- Node 1 has boolean rightThread as true, hence next we visit its inOrder successor node 2.
- Node 2 has a right child, so we visit Node 3 next.
- Node 3 does not have a right child, ie the rightThread boolean is true, so we visit Node 4 next.
There are two types of threaded binary tree: Single Threaded Binary Tree. Double Threaded Binary Tree.
What is the predecessor of a node in a tree called? ›All nodes except the root have exactly one predecessor node, called its parent. The root is the only node with no parent. In computer science, it is customary to draw trees growing downward: Because a tree is a recursive data structure, each node in the tree is the root of a subtree.
How to do an inorder traversal of binary tree? ›In an inorder traversal of a binary tree, we traverse one subtree of a node, then "visit" the node, and then traverse its other subtree. Usually, we traverse the node's left subtree first and then traverse the node's right subtree.
What is the predecessor answer? ›Predecessor of a number is the number which comes before that number. The successor is that number which comes after that number. So this is the final answer.
What is the common predecessor of two given nodes in a binary tree? ›
Conclusion. The lowest common ancestor (LCA) of two nodes in a binary tree is the deepest node which is the ancestor of both the nodes.
What is the difference between successor and predecessor of a number and is _____? ›Successor is obtained by adding 1 to the number. And predecessor is obtained by subtracting 1 from the number, so the difference between the predecessor and successor is 1 + 1 = 2.
What is the immediate successor of a node called? ›Child of a node: The immediate successor of a node is known as a child of a node. Leaf node: The leaf node is a node that does not have any child node. It is also known as an external node. Non-leaf node: The non-leaf node is a node that has atleast one child node.
What is inorder successor and inorder predecessor with respect to inorder threaded binary tree? ›What is Predecessor and Successor : When you do the inorder traversal of a binary tree, the neighbors of given node are called Predecessor(the node lies behind of given node) and Successor (the node lies ahead of given node).
What are the all immediate successors of a node known as? ›All immediate successors of a node are its children. Edge is a connection between one node to another. It is a line between two nodes or a node and a leaf. Nodes with the same parent are called Siblings.
Is predecessor and successor the same? ›Predecessor refers to the previous term of a particular term while the successor refers to the next term of a particular term. In order to find the successor of a whole number, one must add one to the particular given number. In order to find a predecessor, one must subtract one from the particular given number.
What is the successor and predecessor of the 3 digit number? ›The largest 3 digit number is 999. [0. 5 mark]Therefore, the successor of 999 is, ⇒ 999+ 1 =1000 [0. 5 mark]The smallest 3 digit number is 100 [0.
What is preorder traversal example? ›In left subtree of 30, there is an element 25, so print 25, and traverse the left subtree of 25. In left subtree of 25, there is an element 15, and 15 has no subtree. So, print 15, and move to the right subtree of 25. In right subtree of 25, there is 28, and 28 has no subtree.
What is a preorder traversal of a general tree? ›Preorder traversal of a general tree first visits the root of the tree, then performs a preorder traversal of each subtree from left to right. A postorder traversal of a general tree performs a postorder traversal of the root's subtrees from left to right, then visits the root.
Which is correct preorder traversal? ›The correct solution is 'option 1'. Visit the root node. Traverse the left subtree ( call Algo Preorder(left-subtree) ).
What is the preorder complexity of binary tree? ›
If a tree has n nodes, then each node is visited only once in the preorder traversal of binary tree, hence the complexity of the preorder traversal of the binary tree is O ( n ) O(n) O(n).
What is the predecessor in a binary tree? ›What is an in-order predecessor in a binary search tree? The in-order predecessor of a node in a Binary Search Tree is the node that comes before our key node when we write the inorder traversal of the tree.
What is the predecessor of a node in a binary tree called? ›The successors of a node are called its children; the unique predecessor of a node is called its parent. If two nodes have the same parent, they are called brothers or siblings. In a binary tree the two children are called the left and right.
What is the answer of find the successor of 5? ›The successor of 5 is 6.
What is the successor of the successor of 999? ›Thus, the successor of 999 is 1000.
What is preorder and postorder of a binary tree? ›For Preorder, you traverse from the root to the left subtree then to the right subtree. For Post order, you traverse from the left subtree to the right subtree then to the root.
What is preorder function in binary search tree? ›- Preorder = (Root, Left subtree, Right Subtree)
- Inorder = (Left subtree, Root, Right Subtree)
- Postorder = (Left Subtree, Right subtree, Root)
Yes, we can construct a Binary Tree from one traversal only (Inorder or Postorder or Preorder) but we cannot construct an unique Binary Tree from a single traversal (inorder or preorder or postorder).
Is preorder of a binary tree unique? ›Preorder and postorder do not uniquely define a binary tree.