Computer Science 302
Introduction to Data Structures
Spring 2006
Assignment 6

Constructing a Binary Tree from its Inorder and Preorder Traversal

Due Thursday, March 23, 2006.

• It is expected that students will discuss the assignments. But do not turn in code written by another person. If that happens, both persons are violating the ethics of this course. Representing the work of another person as your own is plagiarism, and may result in a disciplinary "F" in the course.
  It is permissable (in this course, as this is up to the instructor) for you to obtain ideas from other students or from other persons. But you must type in the code yourself.
  It is unadvisable for you to allow another student to have an electronic copy of your work, as then you would unwittingly be a party to a breach of these rules. Showing the other student a hard copy is less dangerous.
  The above rule does not apply to copying files that I have made publicly available. I expect that you will use those in their original form or with appropriate modifications (made by just you, of course).
  If you utilize code that you obtain from other sources, be sure to give credit in a comment, such as:
  // this code from website www.mit.edu/help/x13
• This programming assignment deals with binary trees. A binary tree is uniquely determined from two lists of its nodes, preorder and inorder. For example, if the preorder traversal of a binary tree is Bob,Sam,Ted,Ann,Sue,Kim,Meg; and the inorder traversal is Ted,Sam,Ann,Bob,Sue,Meg,Kim; then the tree must look like this.
  Your program should construct a binary tree by reading two sequences, one which is the preorder listing of the nodes of a binary tree, and the other of which is a inorder listing of those same nodes.
  Here are some hints:
  
• Next, your program should write the nodes of the tree in:
  1. postorder: (In the example: Ted,Ann,Sam,Meg,Kim,Sue,Bob)
  2. level order: (In the example: Bob,Sam,Sue,Ted,Ann,Kim,Meg)
  As always, the programs must be executed on our machine, "student".
  If you cannot get your program to run on that machine, even though it works on some other computer, that will be graded the same as non-working code, in other words, partial credit might be given.
• Turn in all files, including a file that shows several sample runs.
  All files must be turned in electronically to Premalatha Reguraman. The deadline for electronic submission is Thursday, March 23. The submission must be timestamped before midnight. You must mail it from your engineering college account.
  Please feel free to email questions about the homework to me or to Miss Reguaraman. Be sure to include the string "CSC 302 Hw6" in the subject field of your email.