Can you reconstruct the tree

Assignment Help Computer Engineering

Reference no: EM132121043

Reconstructing Binary Trees Via Traversals

Recall the binary tree data structure; recall three algorithms for traversing the tree: the inorder traversal, the preorder traversal, and the postorder traversal.

1. Suppose you are given the preorder traversal and the inorder traversal of a binary tree. Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness. If not, give a counter example. Note that a binary tree is not necessarily a binary search tree.

2. Suppose you are given the preorder and postorder traversals of a binary tree. Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness If not, give a counter example.

3. Suppose you are given the preorder traversal of a binary tree. In addition, you are told that the tree is a binary search tree. Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness. If not, give a counter example.

Reference no: EM132121043

Questions Cloud

Explain in detail the characters in product variety concept : Explain in detail the characters in the product variety concept. Give examples to support of yours answers.

Write a function called ismagic that takes a 2d array : Write a function called isMagic that takes a 2D array and returns true if the 2D array is a magic square and false otherwise.

Give an algorithm that randomly permutes an input array a : Give an algorithm that randomly permutes an input array A. What is the run-time of your algorithm?

What are the benefit of using short circuit evaluations : What are the benefit of using short circuit evaluations? Are there are safety/reliability issues involved? If so, what are they?

Can you reconstruct the tree : Can you reconstruct the tree? If so, give an algorithm for doing so and prove its correctness.

Describe three threats to access control : Describe three threats to Access Control from what were covered within the reading and give an example of each.

Business opposed to opening a new venture : What are the advantages of purchasing an existing business opposed to opening a new venture?

Write an application named collegelist : Write an application named CollegeList that declares an array of four "regular" CollegeEmployees, three Faculty, and seven Students.

What are the benefits of franchise to both the franchisee : What are the benefits of franchise to both the franchisee and franchiser and What factors would you consider if interested in buying a franchise?

User Account

All Pages