Completed

# Draw a binary tree containing n nodes whose preorder sequence is the same as its inorder sequence

This project was successfully completed by Topfreelancer4 for \$40 CAD in 5 days.

## Latest Articles

5 days
9
###### Project Description

Good day,

I have this homework to get done (see file attached : Password = s61sbd ).

It needs to be done in JAVA. If you believe you could achieve this, please apply to this job offer. This is part of my first Data structure class in the computer science program.

HERE IS THE QUESTION FOR THIS HOMEWORK.

1. (a)

(10 points) Draw a binary tree containing n nodes whose preorder sequence is the same as its inorder sequence.

(b) (10 points) Draw a binary tree containing n nodes whose inorder sequence is the same as its postorder sequence.

(c) (10 points) Explain why a binary tree with more than one node cannot have the same preorder and postorder sequence.

(*See graph tree)

2. (70 points) One way to deal with the “problem” of NULL pointers in binary trees is to use that space for some other purpose. One example is the threaded binary tree. The threaded binary tree stores with each node two additional bit fields (flags) that indicate if the left and right pointers are to regular (children) nodes or threads. If a left pointer is not a pointer to a child (which in a regular binary tree would be a NULL pointer), then it would store a pointer to the In–order Left–Right successor of that node. The in–order successor of a node is the node that would be processed after the current node in an In–order Left–Right traversal. Similarly, if right pointer is not a pointer to a child (which in a regular binary tree would be a NULL pointer), then it would store a pointer to the In–order Right–Left successor of that node. The in–order successor of a node is the node that would be processed after the current node in an In–order Right–Left traversal. In the figure given above, the In–order Left–Right traversal processes the nodes in the following order: 12, 25, 32, 34, 39, 45, 60, 65, 78, 89 91. The In–order Right–Left traversal processes the nodes in the opposite order from 91 to 12.

The advantage of a threaded tree is that operation of in–order traversal can be implemented without use of recursion or a stack.

Implement the BST as a threaded binary tree. Insert into this BST the elements: 45, 78, 89, 32, 60, 25, 39, 91, 12, 34, 65. Thence, give the In–order Left–Right traversal of the tree.

## Hire Freelancers who also bid on this project

• Forbes
• The New York Times
• Time
• Wall Street Journal
• Times Online