What is the running time of your algorithm

Assignment Help Computer Engineering

Reference no: EM132139769

Question :

Suppose a binary tree T has 10 nodes which are labeled 0,1,2,...,9. We ran the inorder and postorder traversals on the tree and the nodes were processed in the following order: inorder traversal: 0,3,1,2,9,4,6,5,8,7 postorder traversal: 0,1,2,3,4,5,6,7,8,9

a. Draw T with its nodes labeled. (Hint: What is the root node? What nodes are in its left subtree? right subtree?)

b. Now consider the general problem. Suppose T is a binary tree whose n nodes are labeled 0,1,...,n-1. You are given two arrays S1 and S2 that correspond to the order in which the nodes were processed in an inorder and postorder traversals respectively.

Design a recursive algorithm that constructs T from S1 and S2. Note that it is enough for your algorithm to describe the children of each node.

What is the running time of your algorithm?

Reference no: EM132139769

Questions Cloud

Analyze financial statements of a publicly traded company : Assignment - Write a financial analysis for a U.S.-based, publicly traded organization. Analyze the financial statements of a publicly traded company

Find a point estimate for p : Let p represent the proportion of Santa Fe black-on-white potsherds at the excavation site. Find a point estimate for p. (Round your answer to four decimal plac

Design a dynamic programming algorithm : Design a dynamic programming algorithm that finds the minimum number of stamps required. The input to your algorithm is the total desired postage value N.

Would you choose the default system parameters : Would you choose the default system parameters when installing the system software? Explain and support your answer with reasoning.

What is the running time of your algorithm : Design a recursive algorithm that constructs T from S1 and S2. Note that it is enough for your algorithm to describe the children of each node.

How many blocks pf main memory are there : What is the format of a memory address as seen by the cache, that is what are the sizes of the tag, block and offset fields.

Paper - state of the economy effects on assets management : Write a paper of 8-10 pages, double-spaced that discusses the following in detail: The state of the economy's effects on assets' management

What is the format of a memory address as seen : What is the format of a memory address as seen by the cache, that is, what are the sizes of the tag, set, and offset fields?

Write the statement in move of the class car calling : Write the statement in Move() of the class Car calling method Move() of the class Vehicle.

User Account

All Pages