50110. Tree Operations

I'm a slow walker, but I never walk backwards.

Write a program to implement tree operations, including flipping, identical testing, and computing the average leaf depth.

Task Description

Three operations for binary tree are as the follows:

  • Flip: For a binary tree where the left subtree is L and the right subtree is R. To flip this tree means to swap L and R, i.e., now L will be the new right subtree, and the R will be the new left subtree, and then we recursively flip both L and R.

    Before flipping (original tree):


    After flipping (new tree):

    For more example, if there is a binary tree T with node A as the root:

    tree Ttree T

    After flipping tree T, a new tree T' is generated:
    tree T'tree T'

    Note that you need to construct a new binary tree by flipping the original tree. That is, you do not need to flip the tree in-place.

  • Identical: Given two binary trees, check if they are identical. This can be recursively defined as follows. Two trees are identical if the data in the root are the same, and both the left and right subtrees are also identical. Note that the number of nodes of the two trees may be different in the input.

  • Average depth computation: Given a binary tree, compute its average depth. The depth of a node is the length of the path to the root. In other words, the depth of a root node is 0, the depths of its children are 1, and the depths of its grandchildren are 2. The average depth of a tree is the total sum of the depths for all leaves (those nodes without any children) divided by the number of leaves. For example, consider the following tree.

    tree depthtree depth

    The depths of node B and C are 1 since there is only one edges for them to the root. The depths of node D, E, F and G are 2 since they need to go through two edges to the root. Similarly, the depths of node H and I are 3 since they need to pass three edges to the root.

    There are totally four leaves in the tree, which are the nodes D, H, F and I. Thus, the average depth is (the sum of leaves’ depth) / (the number of the leaves) = (2+3+2+3)/4 = 10/4.

Please implement each operation by three functions in operations.c:

  1. For flipping operation, please construct a binary tree and do the operation in the function, Node *FlipTree(...), then return the pointer of the root of the new tree.
  2. For identical operation, please compare tree1 and tree2 in the function, int isIdentical(...), and return an integer either 0 or 1. If tree1 and tree2 are identical, return 1; otherwise, return 0.
  3. For average depth computation, please compute the average depth of the tree in the function, void depthAvg(...), and print the result with the format (the sum of leaves’ depth) / (the number of the leaves).

The prototype of three functions are as followed.

operations.h

#ifndef OPERATION
#define OPERATION
typedef struct Node{
    int n;
    struct Node *left, *right;
} Node;
 
Node *FlipTree(Node *root);
int isIdentical(Node *tree1, Node *tree2);
void depthAvg(Node *root);
#endif

You may use the following main function to test your function.

Main Function 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include "operations.h"
 
void printTree(Node *root) {
  if (root == NULL) {
    printf("NULL\n");
    return;
  }
  printf("%d\n", root->n);
  if (root->left == NULL && root->right == NULL) return;
  printTree(root->left);
  printTree(root->right);
}
 
int main() {
  Node node[9];
 
  for(int i = 0; i < 9; i++){
    node[i].n = i;
    node[i].left = node[i].right = NULL;
  }
 
  node[0].left = &node[1];
  node[0].right = &node[2];
  node[1].left = &node[3];
  node[1].right = &node[4];
  node[2].left = &node[5];
  node[2].right = &node[6];
  node[4].left = &node[7];
  node[6].right = &node[8];
 
  Node *tree = FlipTree(&node[0]);
  printTree(&node[0]);
  printTree(tree);
 
  return 0;
}

Main Function 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include "operations.h"
 
int main() {
  Node tree1[9];
  Node tree2[9];
 
  for(int i = 0; i < 9; i++){
    tree1[i].n = tree2[i].n = i;
    tree1[i].left = tree1[i].right = NULL;
    tree2[i].left = tree2[i].right = NULL;
  }
 
  tree1[0].left = &tree1[1];
  tree1[0].right = &tree1[2];
  tree1[1].left = &tree1[3];
  tree1[1].right = &tree1[4];
  tree1[2].left = &tree1[5];
  tree1[2].right = &tree1[6];
  tree1[4].left = &tree1[7];
  tree1[6].right = &tree1[8];
 
  tree2[0].left = &tree2[1];
  tree2[0].right = &tree2[2];
  tree2[1].left = &tree2[3];
  tree2[1].right = &tree2[4];
  tree2[2].left = &tree2[5];
  tree2[2].right = &tree2[8];
  tree2[4].left = &tree2[6];
  tree2[6].right = &tree2[7];
 
  printf("%d\n", isIdentical(&tree1[0], &tree2[0]));
  printf("%d\n", isIdentical(&tree1[0], &tree1[0]));
  return 0;
}

Main Function 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include "operations.h"
 
int main() {
  Node tree1[9];
 
  for(int i = 0; i < 9; i++){
    tree1[i].n = i;
    tree1[i].left = tree1[i].right = NULL;
  }
 
  tree1[0].left = &tree1[1];
  tree1[0].right = &tree1[2];
  tree1[1].left = &tree1[3];
  tree1[1].right = &tree1[4];
  tree1[2].left = &tree1[5];
  tree1[2].right = &tree1[8];
  tree1[4].left = &tree1[6];
  tree1[6].right = &tree1[7];
 
  depthAvg(&tree1[0]);
 
  return 0;
}

Compile

gcc -std=c99 -O2 main.c operations.c

Subtask

  • 30 points: To implement the flip operation.
  • 25 points: To implement the identical testing operation.
  • 45 points: To compute the average depth.

Note

It is guaranteed that only the specific function will be executed for each subtask. For example, you can implement only the flip operation and isIdentical function is incomplete in operations.c. However, you need to check if your operations.c could compiled. Otherwise, you will get a CE (compile error).

Input Format

  • 0 < the number of nodes for each tree < 100001.

Output Format

Print the result of each operation.

Sample Output 1

0
1
3
4
7
NULL
2
5
6
NULL
8
0
2
6
8
NULL
5
1
4
NULL
7
3

Sample Output 2

0
1

Sample Output 3

10/4

Discussion