Introduction

The programme is supposed to build a binary search tree according to the information given by the administrator and fill into the tree with the interger keys given in a unique way determined by the structrue of the tree.The keys should thus be rearranged and output by a level order travesal of the BST.
Our report is aimed at illstrating how we solved the problem in a comparable simple way with the shortest time bound. It shows a possible application of the binary search tree we have learned about.

Algorithm Specification

We first build the BST as below.
Node[i] stores the address of the corresponding struct of the ith node.
Build tree

for i in 0...n-1 
    Input LeftSon,RightSon.
    if LeftSon eq. -1
        Set Node[i] -> ls as NULL;
    else 
        Set Node[i] -> ls as Node[LeftSon], Judge[LeftSon] as true;
    if RightSon eq. -1                        
        Set Node[i] -> rs as NULL;      
    else 
        Set Node[i] -> rs as Node[RightSon], Judge[RightSon] as true;
    Set Node[i] -> Size as 1;

This for loop iterated n times,so the time complexity is $O(N)$.

Since we are supposed to output the keys in specific order,we now deal with the given intergers.
Sort the numbers

1
2
3

for i in 0...n-1
    input val[i]   
sort val array;

Here we use library function sort, and the time complexity is $O(nlogn)$.

It’s clear that each key correspands to an identity from 0 to 8. As we have sorted the value of keys before, we now need to know the rank of every node in the BST so that we can put the keys into them. After some discussion, we believe the rank can be decided by two variables named $Size$ and $k$. $Size_u$ means the number of all nodes in the subtree whose root is node u.
k is the number of nodes which are not in the subtree u but their value are smaller than the node u’s.
Get Size
We can use a DFS(deep first search) to get the Size of every subtree. When we are dealing with the node u, we should first deal with its children.

function dfs(PtrToNode u) 
    if u -> ls not equals to NULL
        dfs(u -> ls);
    if u -> Rs not equals to NULL
        dfs(u -> rs);
    u -> Size equals to 1 + Get_Size(u -> ls) + Get_Size(u -> rs);

Get_Size(u) ==> if u == NULL, 0 else u -> Size
Each node is visited only once, so the time complexity is $O(N)$.

Get k and rank
As we can see, what we need is the rank of each node in the tree, so that we can decide which key to put in it. To get the rank, we first have to learn about all the nodes whose value is smaller than the current node. So we generally divide them into two parts————the nodes that are in this subtree whose value is smaller than its and those that are not but still satisfies the value condition. Suppose the current node as the root of a subtree, it’s clear that all the descendants of its left child and the left child itself are smaller than the root. And the number of the qualified nodes, in this situation, is the Size of the left son which we have calculated before in another function. Now we have to get k. First we have to know whether Node u is the left or right son of its parent.If it is a left son, then its value is definitely smaller than the parent’s, not to mention the sibling and its descendants, so no change is to be made to the current k. If it is a right son, than the Size of its parent has to be plused.
Thus, till now we have already got all we need to caculate the rank of Node u, and all the work is done by a single function as below.

Solve(PtrToNode u, int k) 
    set rank as (Get_Size(u -> ls) + k + 1);     
    set u -> val as val[rank - 1];               
    if (u -> ls) 
        call Solve(u -> ls, k);       
    if (u -> rs) 
        call Solve(u -> rs, k + Get_Size(u -> ls) + 1);

Here each node is visited only once as well, so the time complexity is $O(N)$.

Testing Results

Case 1:

8
 1  5
 2  3
-1 -1
 4 -1
-1 -1
-1  6
-1  7
-1 -1
13 57 23 86 55 35 29 77

A random case to test if the programme is able to work properly.
The expected output is 55 23 57 13 35 77 29 86.
Program output is 55 23 57 13 35 77 29 86.
Status: Pass.

Case 2:

7 
 1  5
-1  2
 3  4
-1 -1
-1 -1
-1  6
-1 -1
58 11 20 39 65 77 42

A random case to test if the programme is able to work properly.
The expected output is 58 11 65 39 77 20 42.
Program output is 58 11 65 39 77 20 42.
Status: Pass.

Case 3:

10
1 2
3 -1
4 9
8 -1
5 -1
6 7
-1 -1
-1 -1
-1 -1
-1 -1
5 1 94 51 30 20 20 8 74 57

A random case to test if the programme is able to work properly.
The expected output is 20 8 74 5 57 94 1 30 20 51.
Program output is 20 8 74 5 57 94 1 30 20 51.
Status: Pass.

Case 4:

5
 1 -1
 2 -1
 3 -1
 4 -1
-1 -1
18 34 15 26 8

A special case where a tree chain is built to test if the programme is able to work properly.
The expected output is 34 26 18 15 8.
Program output is 34 26 18 15 8.
Status: Pass.

Case 5:

7
 1  4
 2  3
-1 -1
-1 -1
 5  6
-1 -1
-1 -1
18 91 60 54 23 48 12

A special case where a perfect binary tree is built to test if the programme is able to work properly.
The expected output is 48 18 60 12 23 54 91.
Program output is 48 18 60 12 23 54 91.
Status: Pass.

Analysis and Comments

First, our program use dynamic memory application, we malloc $n sizeof(node)$ memory as a memory pool to speed accelerate every node get their address of struct node, if not, every node will use malloc and the time cost will increase. The time complexity of memory application is $O(1)$ and build tree structure is $O(n)$. The memory used there is $n sizeof(node)$ + $n * size_t$ bytes, so the space complexity there is $O(n)$.
Then, we use library function sort to get n integer sorted. The complexity of this process is $O(nlogn)$, and there we use a n size array to store the integer and get them sorted, the space complexity is $O(n)$.
Next, we use a recursive function to calc every subtree’s size. In this process, every node will be visited only once, so the time complexity of this process is $O(n)$. We use a n size int array to store every subtree’s node, so the space complexity of this process is $O(n)$.
After that, we use another recursive function to calc every node’s rank in the tree , with the help of array size, we can calc every node’s rank rk in $O(1)$, and set its value to the rkth largest value. Because the val array is sorted, so we can use $val_{rank-1}$ to get the rkth largest value easily. The same as above, every node will be visited only once and the time complexity is $O(n)$, and we just use constant extra space. So the space complexity of this is $O(1)$.
Last, we use a queue to print the level order traversal sequence of that tree. The time complexity is $O(n)$ and space complexity is $O(n)$.
Thus, the program’s time complexity is $O(nlogn)$ and space complexity is $O(n)$.
First this algorithm consider some case of the error input such as don’t construct a tree or construct a forest. There may be other cases we didn’t considered. Second, the time complexity of this algorithm is very excellent, the limit of the time complexity is time complexity of quick sort, maybe we can use special sort method for special data to get more excellent time complexity.

Declaration
We hereby declare that all the work done in this project titled
“Build a Binary Search Tree” is of our independent effort as a group.