Find Preorder Successor in a Threaded Binary Tree

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:

1. If the node has a thread to its successor, return the successor node.
2. If the node has a right child, return the right child.
3. If the node is the left child of its parent and the parent has a right child, return the right child of the parent.
4. 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.
5. 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.
6. 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: