Course Content
C Tutorial
About Lesson

Trees (Binary Trees, Binary Search Trees)

Binary trees are fundamental data structures used in computer science, particularly in C programming. They consist of nodes, each containing a value and references to two children nodes: the left child and the right child. In C, binary trees can be implemented using structures and pointers.

Structure of a Binary Tree Node in C

In C, a binary tree node can be defined using a structure:

struct Node {
int data;
struct Node* left;
struct Node* right;
};

Here, data represents the value stored in the node, while left and right are pointers to the left and right child nodes, respectively.

Implementing Binary Search Trees (BSTs) in C

Binary search trees are a specific type of binary tree where the left child of a node contains a value lesser than the node’s value, and the right child contains a value greater than the node’s value.

Insertion Operation in a BST

In C, the insertion operation in a BST involves recursively traversing the tree to find the appropriate position for the new node based on its value:

struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}

return root;
}

Searching in a Binary Search Tree (BST)

Searching for a value in a BST follows a similar recursive approach:

struct Node* search(struct Node* root, int value) {
if (root == NULL || root->data == value) {
return root;
}

if (value < root->data) {
return search(root->left, value);
} else {
return search(root->right, value);
}
}

Traversing a Binary Tree

There are several ways to traverse a binary tree in C. Some common methods include:

Inorder Traversal

In inorder traversal, nodes are visited in the order: left subtree, root, right subtree.

void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

Preorder Traversal

Preorder traversal visits the root node first, then the left and right subtrees.

void preorderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

Postorder Traversal

Postorder traversal visits the left and right subtrees before the root node.

void postorderTraversal(struct Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}