Can you write this code in Pseudo code? the program is written in C language - #

Question

Can you write this code in Pseudo code?

the program is written in C language -

#include <stdio.h>
#include <stdlib.h>

struct Node
{
int Value;
struct Node* Left;
struct Node* Right;
struct Node* Parent;
};

struct Node * minValue(struct Node* Node);

struct Node * inOrderSuccessor(struct Node *Root, struct Node *n)
{
// step 1 of the above algorithm
if( n->Right != NULL )
return minValue(n->Right);

// step 2 of the above algorithm
struct Node *p = n->Parent;
while(p != NULL && n == p->Right)
{
n = p;
p = p->Parent;
}
return p;
}

struct Node * minValue(struct Node* Node)
{
struct Node* current = Node;
  
// loop down to find the Leftmost leaf
while (current->Left != NULL)
{
current = current->Left;
}
return current;
}

//Helper function that allocates a new Node with the given Value and NULL Left and Right pointers
struct Node* newNode(int Value)
{
struct Node* Node = (struct Node*)malloc(sizeof(struct Node));
Node->Value = Value;
Node->Left = NULL;
Node->Right = NULL;
Node->Parent = NULL;

return(Node);
}

//function for insertion
struct Node* insert(struct Node* Node, int Value)
{
//in case of empty tree
if (Node == NULL)
return(newNode(Value));
else
{
struct Node *temp;

// Otherwise, recursion on down the tree
if (Value <= Node->Value)
{
temp = insert(Node->Left, Value);
Node->Left = temp;
temp->Parent= Node;
}
else
{
temp = insert(Node->Right, Value);
Node->Right = temp;
temp->Parent = Node;
}
  
//returning unchanged pointer to access all of the Nodes
return Node;
}
}
  
int main()
{
  
struct Node* Root = NULL, *temp, *succ, *min;

//creating the tree given in the above diagram
Root = insert(Root, 20);
Root = insert(Root, 8);
Root = insert(Root, 22);
Root = insert(Root, 4);
Root = insert(Root, 12);
Root = insert(Root, 10);
Root = insert(Root, 14);
temp = Root->Left->Right->Right;

succ = inOrderSuccessor(Root, temp);
if(succ != NULL)
{
printf(" Inorder Successor of %d is %d ", temp->Value, succ->Value);
}
else
{
printf(" Inorder Successor doesn't exist ");
}
return 0;
}

Explanation / Answer

This program is finding the Inorder success of a node present in the tree:

Inorder Successor:

Inorder successor is defined as while doing a inorder traversal of a tree the node comes after a given node is called as its Inorder Successor and the node comes before a given node is called as its Inorder Successor.

This program sudo code goes like this:

1)Created a tree first with nodes.

2)Called the inorder successor function of the node for which we want to find the Inorder successor.

.2.1)The inorder sucessor always lies in the right child leftest node i.e the right child minimum value in a Binary search tree and if that is not present then its parent node will be its inorder successor.

3)The minValue function is used here to find the leftest node of the right child.

Note: This program is first creating a Binary Search Tree which has a property that every node is greater than its left child and every node is smaller than its right child.

So here we first declare a tree using structure with 3 fields left child, right child and its parent child,

Then we called the insert method to each node to place them in their right position so that this property remains maintained and then over this we can call our inorder successor function to find inorder successor of a given node.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.