Write pseudocode to output the nodes in order for the optimal binary search tree

ID: 3601240 • Letter: W

Question

Write pseudocode to output the nodes in order for the optimal binary search tree given the r(i,j) array (the array that holds the root choices during the construction of the A array). The ordering should be top to bottom, left to right as shown below. Explain that this can be done in O(n) time. Example BST with nodes numbered:

The output should look like:
1,dog
2,cat
3,frog
4,bird
5,cow
6,(empty)
7,goat
8,(empty)
9,(empty)
10,cheetah
11,dingo
12,(empty)
13,(empty)
14,gecko
15,hamster

dog,1 cat,2 frog,3 bird,4 (empty),6 (empty),12 (empty),13 gecko,14 hamster,15 cow,5 goat,7 (empty),8 (empty),9cheetah, 10 dingo,11

Explanation / Answer

The following levelorder traversal of the tree will give the required order.The
complexity will be O(n) as each node is visted once.

void printLevelOrder(struct node* root)
{
    int h = height(root);
    int i;
    for (i=1; i<=h; i++)
        printLevel(root, i);
}

void printLevel(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1)
    {
        printLevel(root->left, level-1);
        printLevel(root->right, level-1);
    }
}

int height(struct node* node)
{
    if (node==NULL)
        return 0;
    else
    {

        int leftheight = height(node->left);
        int rightheight = height(node->right);

        if (leftheight > rheight)
            return(leftheight+1);
        else return(rightheight+1);
    }
}

Navigate

Write pseudocode to design a phone contact list program. This is to be in Pseudo

Write pseudocode to read in a set of numbers from a file representing rolls of a

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

Write pseudocode to output the nodes in order for the optimal binary search tree

Question

Explanation / Answer

Related Questions

Navigate