Create a Binary search tree

Properties:

  1. 1.
    leaf -> left < leaf && leaf < leaf->right
  2. 2.
    if traverse as inorder, the sequence will be increasing.

Code:

1
#include <stdio.h>
2
#include <stdlib.h>
3
​
4
struct Node {
5
struct Node* left;
6
struct Node* right;
7
int val;
8
};
9
​
10
​
11
struct Node* newNode(int val){
12
struct Node* new = (struct Node*)malloc(sizeof(struct Node));
13
​
14
new->val = val;
15
new->left = NULL;
16
new->right = NULL;
17
return new;
18
}
19
​
20
​
21
struct Node* insertBST(struct Node* head, int val){
22
if(head == NULL){
23
return newNode(val);
24
}
25
​
26
if(val < head->val){
27
head->left = insertBST(head->left, val);
28
}else if (val > head->val) {
29
head->right = insertBST(head->right, val);
30
}
31
​
32
return head;
33
}
34
​
35
​
36
void inorder(struct Node* head){
37
​
38
if(head != NULL){
39
inorder(head->left);
40
printf("Node: %d\n", head->val);
41
inorder(head->right);
42
}
43
}
Copied!

Test code:

1
int main() {
2
3
struct Node* root = NULL;
4
​
5
root = insertBST(root, 7853);
6
insertBST(root, 30);
7
insertBST(root, 999);
8
insertBST(root, 40);
9
insertBST(root, -9);
10
insertBST(root, 70);
11
insertBST(root, -999);
12
insertBST(root, 80);
13
​
14
inorder(root);
15
​
16
return 0;
17
}
Copied!

Reference:

Copy link