Binary Tree Traversals
/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
/* === Binary Tree Node ============================================= */
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
/* Function prototypes */
TreeNode *new_node(int val);
void preorder_traversal(TreeNode *root, int *out, int *cnt);
void inorder_traversal(TreeNode *root, int *out, int *cnt);
void postorder_traversal(TreeNode *root, int *out, int *cnt);
/**
* @brief Allocate a new tree node.
*/
TreeNode *new_node(int val) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
/**
* @brief Append preorder traversal values to out[].
* @param root current node (may be NULL)
* @param out output array (pre-allocated to size n)
* @param cnt current write index, updated in place
*/
void preorder_traversal(TreeNode *root, int *out, int *cnt) {
// WRITE YOUR CODE HERE
}
/**
* @brief Append inorder traversal values to out[].
* @param root current node (may be NULL)
* @param out output array (pre-allocated to size n)
* @param cnt current write index, updated in place
*/
void inorder_traversal(TreeNode *root, int *out, int *cnt) {
// WRITE YOUR CODE HERE
}
/**
* @brief Append postorder traversal values to out[].
* @param root current node (may be NULL)
* @param out output array (pre-allocated to size n)
* @param cnt current write index, updated in place
*/
void postorder_traversal(TreeNode *root, int *out, int *cnt) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
static void print_arr(int *arr, int n) {
for (int i = 0; i < n; ++i) {
if (i) putchar(' ');
printf("%d", arr[i]);
}
putchar('\n');
}
int main(void) {
int n;
scanf("%d", &n);
int *lc = (int *)calloc((size_t)(n + 1), sizeof(int));
int *rc = (int *)calloc((size_t)(n + 1), sizeof(int));
for (int i = 1; i <= n; ++i)
scanf("%d %d", &lc[i], &rc[i]);
/* allocate one TreeNode per index */
TreeNode **nodes = (TreeNode **)malloc((size_t)(n + 1) * sizeof(TreeNode *));
for (int i = 1; i <= n; ++i) nodes[i] = new_node(i);
/* wire up children */
for (int i = 1; i <= n; ++i) {
nodes[i]->left = lc[i] ? nodes[lc[i]] : NULL;
nodes[i]->right = rc[i] ? nodes[rc[i]] : NULL;
}
/* find root: the unique node that is nobody's child */
int *isChild = (int *)calloc((size_t)(n + 1), sizeof(int));
for (int i = 1; i <= n; ++i) {
if (lc[i]) isChild[lc[i]] = 1;
if (rc[i]) isChild[rc[i]] = 1;
}
int root_idx = 1;
for (int i = 1; i <= n; ++i)
if (!isChild[i]) { root_idx = i; break; }
TreeNode *root = nodes[root_idx];
int *out = (int *)malloc((size_t)n * sizeof(int));
int cnt;
cnt = 0; preorder_traversal (root, out, &cnt); print_arr(out, n);
cnt = 0; inorder_traversal (root, out, &cnt); print_arr(out, n);
cnt = 0; postorder_traversal(root, out, &cnt); print_arr(out, n);
for (int i = 1; i <= n; ++i) free(nodes[i]);
free(nodes);
free(lc);
free(rc);
free(isChild);
free(out);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Binary Tree Traversals
Given a binary tree with $n$ nodes (numbered $1$ to $n$), output its **preorder**, **inorder**, and **postorder** traversal sequences. The value stored at node $i$ is $i$ itself.
### Input
- The first line contains an integer $n$ ($1 \leq n \leq 10000$), the number of nodes.
- The next $n$ lines describe the tree structure. The $i$-th of these lines contains two integers $l$ and $r$, representing the left and right children of node $i$ respectively ($0$ if node $i$ has no left or right child).
- It is guaranteed that the input describes a valid binary tree with exactly one root.
### Output
Three lines:
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
Each line contains $n$ space-separated integers.
### Example
**Input**
```
7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
```
**Output**
```
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
```
**Explanation**
The input describes the following tree (node values equal their indices):
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
Submit