C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Learn tree data structure in C with BST implementation covering insertion, deletion, searching, inorder/preorder/postorder traversals, and tree operations.
A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures like arrays and linked lists, trees allow us to represent hierarchical relationships and enable efficient searching, sorting, and insertion operations. The Binary Search Tree (BST) is the most commonly used tree variant.
Tree Terminology
| Term | Definition |
|---|---|
| Root | Top node with no parent |
| Node | Element containing data and child pointers |
| Leaf | Node with no children |
| Height | Longest path from root to leaf |
| Depth | Distance from root to a node |
| Subtree | A node and all its descendants |
| Degree | Number of children a node has |
Binary Search Tree Properties
A BST maintains this invariant: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This allows O(log n) search, insertion, and deletion on average.
Complete BST Implementation
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// Create a new node
TreeNode* createNode(int data) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
// Insert a value into BST
TreeNode* insert(TreeNode *root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
// Duplicates are ignored
return root;
}
// Search for a value
TreeNode* search(TreeNode *root, int key) {
if (root == NULL || root->data == key)
return root;
if (key < root->data)
return search(root->left, key);
return search(root->right, key);
}
// Find minimum value node
TreeNode* findMin(TreeNode *root) {
while (root && root->left != NULL)
root = root->left;
return root;
}
// Find maximum value node
TreeNode* findMax(TreeNode *root) {
while (root && root->right != NULL)
root = root->right;
return root;
}
// Delete a node from BST
TreeNode* deleteNode(TreeNode *root, int key) {
if (root == NULL) return NULL;
if (key < root->data) {
root->left = deleteNode(root->left, key);
} else if (key > root->data) {
root->right = deleteNode(root->right, key);
} else {
// Node found - handle 3 cases
// Case 1: Leaf node
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
// Case 2: One child
else if (root->left == NULL) {
TreeNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode *temp = root->left;
free(root);
return temp;
}
// Case 3: Two children - replace with inorder successor
else {
TreeNode *successor = findMin(root->right);
root->data = successor->data;
root->right = deleteNode(root->right, successor->data);
}
}
return root;
}
// Inorder Traversal (Left, Root, Right) - gives sorted order
void inorder(TreeNode *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// Preorder Traversal (Root, Left, Right) - for tree serialization
void preorder(TreeNode *root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// Postorder Traversal (Left, Right, Root) - for deletion
void postorder(TreeNode *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
// Calculate height of tree
int height(TreeNode *root) {
if (root == NULL) return -1;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// Count total nodes
int countNodes(TreeNode *root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
// Count leaf nodes
int countLeaves(TreeNode *root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
// Free entire tree
void freeTree(TreeNode *root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
TreeNode *root = NULL;
// Build BST
int values[] = {50, 30, 70, 20, 40, 60, 80, 10, 35};
for (int i = 0; i < 9; i++)
root = insert(root, values[i]);
printf("Inorder (sorted): ");
inorder(root);
printf("\n");
printf("Preorder: ");
preorder(root);
printf("\n");
printf("Postorder: ");
postorder(root);
printf("\n");
printf("\nHeight: %d\n", height(root));
printf("Total nodes: %d\n", countNodes(root));
printf("Leaf nodes: %d\n", countLeaves(root));
printf("Min: %d, Max: %d\n", findMin(root)->data, findMax(root)->data);
// Search
TreeNode *found = search(root, 40);
printf("\nSearch 40: %s\n", found ? "Found" : "Not Found");
found = search(root, 45);
printf("Search 45: %s\n", found ? "Found" : "Not Found");
// Delete
printf("\nAfter deleting 30 (node with 2 children):\n");
root = deleteNode(root, 30);
printf("Inorder: ");
inorder(root);
printf("\n");
freeTree(root);
return 0;
}
Output
Inorder (sorted): 10 20 30 35 40 50 60 70 80 Preorder: 50 30 20 10 40 35 70 60 80 Postorder: 10 20 35 40 30 60 80 70 50 Height: 3 Total nodes: 9 Leaf nodes: 4 Min: 10, Max: 80 Search 40: Found Search 45: Not Found After deleting 30 (node with 2 children): Inorder: 10 20 35 40 50 60 70 80
Level Order Traversal (BFS)
c example
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
TreeNode* createNode(int data) {
TreeNode *n = malloc(sizeof(TreeNode));
n->data = data; n->left = n->right = NULL;
return n;
}
// Queue for BFS
typedef struct QNode {
TreeNode *treeNode;
struct QNode *next;
} QNode;
typedef struct { QNode *front, *rear; } Queue;
void enqueue(Queue *q, TreeNode *node) {
QNode *n = malloc(sizeof(QNode));
n->treeNode = node; n->next = NULL;
if (!q->rear) { q->front = q->rear = n; return; }
q->rear->next = n;
q->rear = n;
}
TreeNode* dequeue(Queue *q) {
if (!q->front) return NULL;
QNode *temp = q->front;
TreeNode *node = temp->treeNode;
q->front = temp->next;
if (!q->front) q->rear = NULL;
free(temp);
return node;
}
void levelOrder(TreeNode *root) {
if (!root) return;
Queue q = {NULL, NULL};
enqueue(&q, root);
while (q.front) {
TreeNode *curr = dequeue(&q);
printf("%d ", curr->data);
if (curr->left) enqueue(&q, curr->left);
if (curr->right) enqueue(&q, curr->right);
}
printf("\n");
}
int main() {
TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Level Order: ");
levelOrder(root);
return 0;
}Output
Level Order: 1 2 3 4 5 6 7
Traversal Comparison
| Traversal | Order | Use Case |
|---|---|---|
| Inorder | Left → Root → Right | Get sorted elements from BST |
| Preorder | Root → Left → Right | Create a copy of tree, serialize |
| Postorder | Left → Right → Root | Delete tree, evaluate expressions |
| Level Order | Level by level (BFS) | Find shortest path, level-wise ops |
Interview Questions on Trees
Q1: How do you check if a binary tree is a valid BST? Use inorder traversal and verify that each element is greater than the previous. Or use min/max bounds recursively.
Q2: What's the time complexity of BST operations? Average case: O(log n) for search, insert, delete. Worst case (skewed tree): O(n). Use balanced trees (AVL, Red-Black) for guaranteed O(log n).
Q3: How do you find the Lowest Common Ancestor (LCA) in a BST? Starting from root, if both values are smaller go left, if both are larger go right. When they split, the current node is the LCA.
Q4: Can you convert a sorted array to a balanced BST? Yes – use the middle element as root, recursively build left subtree from the left half and right subtree from the right half.
Q5: What is the difference between a complete and a full binary tree? Complete: all levels are fully filled except possibly the last, which is filled from left. Full: every node has either 0 or 2 children.
Summary
Trees are hierarchical structures that enable efficient O(log n) operations. Binary Search Trees maintain sorted order through their left-smaller, right-larger property. Master the three recursive traversals (inorder, preorder, postorder) and level-order BFS. Understanding deletion with three cases (leaf, one child, two children) is essential for interviews. For production code, consider self-balancing variants like AVL or Red-Black trees to avoid worst-case O(n) behavior.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Trees in C – Binary Search Tree Implementation with Traversals.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, data, structures, trees, trees in c – binary search tree implementation with traversals
Related C Programming Topics
Continue learning this concept
Data Structures In CGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSLearn graph data structure in C with adjacency matrix and adjacency list representations, BFS and DFS traversal algorithms, and complete implementation examples.Data Structures In CHash Tables in C – Implementation, Collision Handling, and ChainingLearn hash table implementation in C with hash functions, collision resolution using chaining and open addressing, performance analysis, and practical examples.Data Structures In CLinked List in C – Singly, Doubly, and Circular with ImplementationComplete guide to implementing linked lists in C covering singly linked list, doubly linked list, circular linked list, all operations with code examples and output.Data Structures In CQueue in C – Linear, Circular, and Priority Queue ImplementationLearn queue data structure in C with linear queue, circular queue, and priority queue implementations using arrays and linked lists with complete code examples.Data Structures In CStack in C – Array and Linked List Implementation with ApplicationsLearn stack data structure in C with array-based and linked list implementations, push/pop operations, applications like expression evaluation, and interview questions.BasicsComments in C ProgrammingLearn about comments in C — single-line comments, multi-line comments, best practices, nested comments, and when to use comments effectively in your code.