Please help me with this question and thank you. Suppose we are given an array P

Question

Please help me with this question and thank you.

Suppose we are given an array P which is known to hold n different integers, as well as an array I of size n whose elements are some permutation of P. For example, P may hold 48, 13, 63, 21, 52, 37, in that order, and I may hold 48, 13, 37, 63, 52, 21. Give the pseudo-code for a recursively defined function HasBinaryTree which takes two such arrays and determines whether there exists a binary tree T whose postorder visit sequence is given by P and whose inorder visit sequence is given by I. An initial call HasBinaryTree(P, 0, I, 0, n) should return True if the given sequences correspond to the post- and inorder sequences of a binary tree. False otherwise. More generally, HasBinaryTree(P, j, I, i, m): Bool should return True if and only if the array segments P[j..(j + m - 1)] and I[i..(i + m - 1)) correspond to the post- and inorder sequences of a binary tree.

Explanation / Answer

This is the function which checks whether the tree is of the post order traversal or not.
For the preorder of the binary tree the following operations are carried-out:-
(i) Visit the root
(ii) Traverse the left subtree, and
(iii) Traverse the right subtree.

The function defined have been implemented on keeping these two pints.

/* The structure shows A binary tree node which has data, pointer to left child
and a pointer to right child
*/

struct node
{
char data;
struct node* left;
struct node* right;
};

check for the tree.
/* This is the Recursive function used to construct the binary tree of size 'n' from
Inorder traversal P[] and Preorder traversal I[]. Initial values
of i and j should be 0 and len -1. The function doesn't
do any error checking for cases where inorder and preorder
do not form a tree */

struct node* Has BinaryTree(int P[], int I[], int i, int j)
{
static int Index = 0;

if(i > j)
return NULL;

/* Pick current node from Preorder traversal using Index
and increment Index */
struct node *tNode = newNode(I[Index++]);

/* If this node has no children then return */
if(i == j)
return tNode;

/* Else find the index of this node in Inorder traversal */
int inIndex = search(P, i, j, tNode->data);

/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = HasBinaryTree(P, pre, i, Index-1);
tNode->right = HasBinaryTree(P, pre, Index+1, j);

/* The 'arr' array variable used here is the original array that should be the output
form the preorder and inorder traversal.
*/

int search(int arr[], int i, int j, int value)
{
int i;
for(i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
return tNode;

}

The tnode which has been retuned is the same array for which it should lead to the preorder and the inorder traversal of the same array.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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