Create a function of the signature: TreeNode* reconsttructTree(int [] preOrderLi

Question

Create a function of the signature:
TreeNode* reconsttructTree(int [] preOrderList, int[] inOrderList);
that returns a pointer to a tree whose pre-order traversal output is given in the array preOrderList and whose in-order traversal output is given in the array inOrderList.

Explanation / Answer

Hey, hope this helps. The print functions were just to test it, as was the main. You can feel free to modify main or remove the print functions if you'd like. Figured I'd include them so you can easily see what is going on. Let me know if you have any questions. Please rate. :) #include using namespace std; class TreeNode { public: int data; TreeNode * left; TreeNode * right; TreeNode() { left = NULL; right = NULL; } }; // recursive method to build a subtree using positions iPre to jPre in the preOrder list // and positions iIn to jIn in the inOrder list TreeNode * buildTree(int preOrder[], int inOrder[], int iPre, int jPre, int iIn, int jIn, int size) { if (jIn data = preOrder[iPre]; //now find this data in the in-order to determine sizes of left and right subtrees int x; for (x = 0; x data) // now x gives the correct position break; } int left = x - iIn; int right = jIn - iIn - x - 1; n->left = buildTree(preOrder, inOrder, iPre+1, iPre+1+left, iIn, iIn+left, size); n->right = buildTree(preOrder, inOrder, iPre+1+left, jPre, iIn+left+1, jIn, size); return n; } // the "n" must be added to the signature so we know how long the arrays are TreeNode * reconstructTree(int preOrderList[], int inOrderList[], int n) { // build the tree using the lists, starting from the full tree of 0 to n return buildTree(preOrderList, inOrderList, 0, n, 0, n, n); } void inOrderPrint(TreeNode * n) { if (n == NULL) return; inOrderPrint(n->left); cout

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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