Trees are one of the most important and versatile data structures in computer science. Among them, the binary tree stands as a fundamental building block—each node has at most two children, traditionally called left and right. Binary trees form the basis for more advanced structures like binary search trees, heaps, and expression trees, and are essential for understanding algorithms, compiler design, and database systems.
What Is a Binary Tree?
A binary tree is a hierarchical data structure where each node contains:
- Data: The value stored in the node
- Left child: Pointer to the left subtree
- Right child: Pointer to the right subtree
Binary Tree Structure: Root ↓ 10 / \ 5 15 / \ \ 3 7 20 Terminology: - Root: Top node (10) - Leaf: Nodes with no children (3, 7, 20) - Parent: Node with children (10, 5, 15) - Child: Nodes descending from another - Subtree: Any node and its descendants
Basic Binary Tree Node Structure
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Basic binary tree node structure
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Creating and Managing Nodes
// Create a new node
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert a node (simple binary tree, not BST)
Node* insertNode(Node *root, int data) {
if (root == NULL) {
return createNode(data);
}
// Simple level-order insertion for demonstration
// (creates a complete binary tree)
Node *queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
Node *current = queue[front++];
if (current->left == NULL) {
current->left = createNode(data);
return root;
} else {
queue[rear++] = current->left;
}
if (current->right == NULL) {
current->right = createNode(data);
return root;
} else {
queue[rear++] = current->right;
}
}
return root;
}
Tree Traversal Methods
Traversal is the process of visiting all nodes in a specific order. There are three main depth-first traversals and one breadth-first traversal.
1. Inorder Traversal (Left-Root-Right)
// Inorder traversal: left, root, right
void inorderTraversal(Node *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
2. Preorder Traversal (Root-Left-Right)
// Preorder traversal: root, left, right
void preorderTraversal(Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
3. Postorder Traversal (Left-Right-Root)
// Postorder traversal: left, right, root
void postorderTraversal(Node *root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}
4. Level Order Traversal (Breadth-First)
// Level order traversal using queue
void levelOrderTraversal(Node *root) {
if (root == NULL) return;
Node *queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
Node *current = queue[front++];
printf("%d ", current->data);
if (current->left) {
queue[rear++] = current->left;
}
if (current->right) {
queue[rear++] = current->right;
}
}
}
Complete Traversal Example:
int main() {
Node *root = NULL;
// Create a simple tree
root = createNode(10);
root->left = createNode(5);
root->right = createNode(15);
root->left->left = createNode(3);
root->left->right = createNode(7);
root->right->right = createNode(20);
printf("Binary Tree Traversals:\n");
printf("Inorder (LNR): ");
inorderTraversal(root);
printf("\n");
printf("Preorder (NLR): ");
preorderTraversal(root);
printf("\n");
printf("Postorder (LRN): ");
postorderTraversal(root);
printf("\n");
printf("Level order: ");
levelOrderTraversal(root);
printf("\n");
return 0;
}
Output:
Binary Tree Traversals: Inorder (LNR): 3 5 7 10 15 20 Preorder (NLR): 10 5 3 7 15 20 Postorder (LRN): 3 7 5 20 15 10 Level order: 10 5 15 3 7 20
Binary Tree Utility Functions
1. Tree Height
// Calculate height of tree (number of edges on longest path)
int treeHeight(Node *root) {
if (root == NULL) {
return -1; // Height of empty tree is -1
}
int leftHeight = treeHeight(root->left);
int rightHeight = treeHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// Number of levels (height + 1)
int numberOfLevels(Node *root) {
return treeHeight(root) + 1;
}
2. Tree Size (Number of Nodes)
// Count total nodes in tree
int treeSize(Node *root) {
if (root == NULL) {
return 0;
}
return 1 + treeSize(root->left) + treeSize(root->right);
}
3. Leaf Nodes Count
// Count leaf nodes (nodes with no children)
int leafCount(Node *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return leafCount(root->left) + leafCount(root->right);
}
4. Check if Tree is Balanced
// Helper function for balanced tree check
int isBalancedHelper(Node *root, bool *balanced) {
if (root == NULL) return 0;
int leftHeight = isBalancedHelper(root->left, balanced);
int rightHeight = isBalancedHelper(root->right, balanced);
if (abs(leftHeight - rightHeight) > 1) {
*balanced = false;
}
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// Check if tree is height-balanced
bool isBalanced(Node *root) {
bool balanced = true;
isBalancedHelper(root, &balanced);
return balanced;
}
5. Find Maximum and Minimum
// Find maximum value in tree
int findMax(Node *root) {
if (root == NULL) {
return -1; // Assuming non-negative values
}
int max = root->data;
int leftMax = findMax(root->left);
int rightMax = findMax(root->right);
if (leftMax > max) max = leftMax;
if (rightMax > max) max = rightMax;
return max;
}
// Find minimum value in tree
int findMin(Node *root) {
if (root == NULL) {
return -1;
}
int min = root->data;
int leftMin = findMin(root->left);
int rightMin = findMin(root->right);
if (leftMin < min) min = leftMin;
if (rightMin < min) min = rightMin;
return min;
}
6. Search for a Value
// Search for a value (linear search, not optimized)
bool search(Node *root, int value) {
if (root == NULL) {
return false;
}
if (root->data == value) {
return true;
}
return search(root->left, value) || search(root->right, value);
}
7. Free Tree Memory
// Free all nodes in tree (postorder traversal)
void freeTree(Node *root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
Complete Utility Example:
int main() {
Node *root = createNode(10);
root->left = createNode(5);
root->right = createNode(15);
root->left->left = createNode(3);
root->left->right = createNode(7);
root->right->right = createNode(20);
printf("Tree Statistics:\n");
printf("Size: %d nodes\n", treeSize(root));
printf("Height: %d\n", treeHeight(root));
printf("Levels: %d\n", numberOfLevels(root));
printf("Leaf nodes: %d\n", leafCount(root));
printf("Is balanced: %s\n", isBalanced(root) ? "Yes" : "No");
printf("Max value: %d\n", findMax(root));
printf("Min value: %d\n", findMin(root));
printf("Search 7: %s\n", search(root, 7) ? "Found" : "Not found");
printf("Search 42: %s\n", search(root, 42) ? "Found" : "Not found");
freeTree(root);
return 0;
}
Binary Search Tree (BST)
A Binary Search Tree is a binary tree with the property:
- All nodes in left subtree are less than current node
- All nodes in right subtree are greater than current node
// BST Node (same structure as binary tree)
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// Create new BST node
BSTNode* createBSTNode(int data) {
BSTNode *newNode = (BSTNode*)malloc(sizeof(BSTNode));
if (!newNode) return NULL;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert into BST (iterative)
BSTNode* insertBSTIterative(BSTNode *root, int data) {
BSTNode *newNode = createBSTNode(data);
if (newNode == NULL) return root;
if (root == NULL) return newNode;
BSTNode *current = root;
BSTNode *parent = NULL;
while (current != NULL) {
parent = current;
if (data < current->data) {
current = current->left;
} else if (data > current->data) {
current = current->right;
} else {
// Duplicate - handle based on requirements
free(newNode);
return root;
}
}
if (data < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
return root;
}
// Insert into BST (recursive)
BSTNode* insertBSTRecursive(BSTNode *root, int data) {
if (root == NULL) {
return createBSTNode(data);
}
if (data < root->data) {
root->left = insertBSTRecursive(root->left, data);
} else if (data > root->data) {
root->right = insertBSTRecursive(root->right, data);
}
// If equal, do nothing (no duplicates)
return root;
}
// Search in BST (efficient)
BSTNode* searchBST(BSTNode *root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchBST(root->left, data);
} else {
return searchBST(root->right, data);
}
}
// Find minimum in BST
BSTNode* findMinBST(BSTNode *root) {
if (root == NULL) return NULL;
while (root->left != NULL) {
root = root->left;
}
return root;
}
// Find maximum in BST
BSTNode* findMaxBST(BSTNode *root) {
if (root == NULL) return NULL;
while (root->right != NULL) {
root = root->right;
}
return root;
}
// Delete node from BST
BSTNode* deleteBST(BSTNode *root, int data) {
if (root == NULL) return root;
// Find the node to delete
if (data < root->data) {
root->left = deleteBST(root->left, data);
} else if (data > root->data) {
root->right = deleteBST(root->right, data);
} else {
// Node found - handle three cases
// Case 1: No child or one child
if (root->left == NULL) {
BSTNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
BSTNode *temp = root->left;
free(root);
return temp;
}
// Case 2: Two children
// Find inorder successor (smallest in right subtree)
BSTNode *temp = findMinBST(root->right);
// Copy the inorder successor's data to this node
root->data = temp->data;
// Delete the inorder successor
root->right = deleteBST(root->right, temp->data);
}
return root;
}
// Check if tree is BST
bool isBSTHelper(BSTNode *root, int min, int max) {
if (root == NULL) return true;
if (root->data < min || root->data > max) return false;
return isBSTHelper(root->left, min, root->data - 1) &&
isBSTHelper(root->right, root->data + 1, max);
}
bool isBST(BSTNode *root) {
return isBSTHelper(root, -1000000, 1000000);
}
// Find lowest common ancestor in BST
BSTNode* findLCA_BST(BSTNode *root, int n1, int n2) {
if (root == NULL) return NULL;
if (root->data > n1 && root->data > n2) {
return findLCA_BST(root->left, n1, n2);
}
if (root->data < n1 && root->data < n2) {
return findLCA_BST(root->right, n1, n2);
}
return root; // This is the LCA
}
int main() {
BSTNode *bstRoot = NULL;
// Insert values
int values[] = {50, 30, 70, 20, 40, 60, 80};
for (int i = 0; i < 7; i++) {
bstRoot = insertBSTRecursive(bstRoot, values[i]);
}
printf("BST Inorder: ");
inorderTraversal(bstRoot); // Should print sorted order
printf("\n");
// Search
int searchVal = 40;
BSTNode *found = searchBST(bstRoot, searchVal);
printf("Search %d: %s\n", searchVal, found ? "Found" : "Not found");
// Min and Max
BSTNode *min = findMinBST(bstRoot);
BSTNode *max = findMaxBST(bstRoot);
printf("Min: %d, Max: %d\n", min->data, max->data);
// Delete
printf("Deleting 30...\n");
bstRoot = deleteBST(bstRoot, 30);
printf("Inorder after deletion: ");
inorderTraversal(bstRoot);
printf("\n");
// Check if BST
printf("Is BST: %s\n", isBST(bstRoot) ? "Yes" : "No");
// LCA
int lca = findLCA_BST(bstRoot, 20, 60)->data;
printf("LCA of 20 and 60: %d\n", lca);
freeTree(bstRoot);
return 0;
}
Advanced Binary Tree Problems
1. Diameter of Binary Tree
// Diameter: longest path between any two nodes
int diameterHelper(Node *root, int *height) {
if (root == NULL) {
*height = 0;
return 0;
}
int leftHeight = 0, rightHeight = 0;
int leftDiameter = diameterHelper(root->left, &leftHeight);
int rightDiameter = diameterHelper(root->right, &rightHeight);
*height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
int throughRoot = leftHeight + rightHeight;
int maxDiameter = leftDiameter > rightDiameter ? leftDiameter : rightDiameter;
return maxDiameter > throughRoot ? maxDiameter : throughRoot;
}
int treeDiameter(Node *root) {
int height = 0;
return diameterHelper(root, &height);
}
2. Path Sum Problems
// Check if there's a root-to-leaf path with given sum
bool hasPathSum(Node *root, int sum) {
if (root == NULL) {
return false;
}
if (root->left == NULL && root->right == NULL) {
return sum == root->data;
}
return hasPathSum(root->left, sum - root->data) ||
hasPathSum(root->right, sum - root->data);
}
// Print all root-to-leaf paths
void printArray(int path[], int pathLen) {
for (int i = 0; i < pathLen; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
void printPathsHelper(Node *root, int path[], int pathLen) {
if (root == NULL) return;
path[pathLen] = root->data;
pathLen++;
if (root->left == NULL && root->right == NULL) {
printArray(path, pathLen);
} else {
printPathsHelper(root->left, path, pathLen);
printPathsHelper(root->right, path, pathLen);
}
}
void printAllPaths(Node *root) {
int path[1000];
printPathsHelper(root, path, 0);
}
3. Mirror and Symmetry
// Create mirror of tree
Node* mirrorTree(Node *root) {
if (root == NULL) return NULL;
Node *leftMirror = mirrorTree(root->left);
Node *rightMirror = mirrorTree(root->right);
root->left = rightMirror;
root->right = leftMirror;
return root;
}
// Check if tree is symmetric (mirror of itself)
bool isMirror(Node *left, Node *right) {
if (left == NULL && right == NULL) return true;
if (left == NULL || right == NULL) return false;
return (left->data == right->data) &&
isMirror(left->left, right->right) &&
isMirror(left->right, right->left);
}
bool isSymmetric(Node *root) {
if (root == NULL) return true;
return isMirror(root->left, root->right);
}
4. Build Tree from Traversals
// Build tree from inorder and preorder traversals
int searchIndex(int arr[], int start, int end, int value) {
for (int i = start; i <= end; i++) {
if (arr[i] == value) return i;
}
return -1;
}
Node* buildFromInorderPreorder(int inorder[], int preorder[],
int inStart, int inEnd, int *preIndex) {
if (inStart > inEnd) return NULL;
Node *node = createNode(preorder[*preIndex]);
(*preIndex)++;
if (inStart == inEnd) return node;
int inIndex = searchIndex(inorder, inStart, inEnd, node->data);
node->left = buildFromInorderPreorder(inorder, preorder,
inStart, inIndex - 1, preIndex);
node->right = buildFromInorderPreorder(inorder, preorder,
inIndex + 1, inEnd, preIndex);
return node;
}
Node* buildFromPostorderInorder(int inorder[], int postorder[],
int inStart, int inEnd, int *postIndex) {
if (inStart > inEnd) return NULL;
Node *node = createNode(postorder[*postIndex]);
(*postIndex)--;
if (inStart == inEnd) return node;
int inIndex = searchIndex(inorder, inStart, inEnd, node->data);
node->right = buildFromPostorderInorder(inorder, postorder,
inIndex + 1, inEnd, postIndex);
node->left = buildFromPostorderInorder(inorder, postorder,
inStart, inIndex - 1, postIndex);
return node;
}
5. Level with Maximum Sum
int maxLevelSum(Node *root) {
if (root == NULL) return 0;
Node *queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
int maxSum = root->data;
int maxLevel = 0;
int currentLevel = 0;
while (front < rear) {
int levelSize = rear - front;
int levelSum = 0;
for (int i = 0; i < levelSize; i++) {
Node *current = queue[front++];
levelSum += current->data;
if (current->left) queue[rear++] = current->left;
if (current->right) queue[rear++] = current->right;
}
if (levelSum > maxSum) {
maxSum = levelSum;
maxLevel = currentLevel;
}
currentLevel++;
}
printf("Maximum sum %d at level %d\n", maxSum, maxLevel);
return maxSum;
}
Complete Binary Tree Implementation
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
// Complete binary tree using array (heap-like)
typedef struct {
int *array;
int capacity;
int size;
} CompleteBinaryTree;
// Create complete binary tree
CompleteBinaryTree* createCompleteTree(int capacity) {
CompleteBinaryTree *tree = malloc(sizeof(CompleteBinaryTree));
tree->array = malloc(capacity * sizeof(int));
tree->capacity = capacity;
tree->size = 0;
return tree;
}
// Insert into complete binary tree (maintains completeness)
void insertComplete(CompleteBinaryTree *tree, int data) {
if (tree->size >= tree->capacity) {
printf("Tree full!\n");
return;
}
tree->array[tree->size] = data;
tree->size++;
}
// Get parent index
int parent(int index) {
return (index - 1) / 2;
}
// Get left child index
int leftChild(int index) {
return 2 * index + 1;
}
// Get right child index
int rightChild(int index) {
return 2 * index + 2;
}
// Print array representation
void printCompleteTree(CompleteBinaryTree *tree) {
printf("Array representation: ");
for (int i = 0; i < tree->size; i++) {
printf("%d ", tree->array[i]);
}
printf("\n");
// Print tree structure (simple level format)
int level = 0;
int printed = 0;
printf("Tree structure:\n");
while (printed < tree->size) {
int levelSize = pow(2, level);
for (int i = 0; i < levelSize && printed < tree->size; i++) {
printf("%d ", tree->array[printed++]);
}
printf("\n");
level++;
}
}
int main() {
CompleteBinaryTree *tree = createCompleteTree(20);
int values[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
for (int i = 0; i < 9; i++) {
insertComplete(tree, values[i]);
}
printCompleteTree(tree);
printf("Parent of index 3 (%d): index %d (%d)\n",
tree->array[3], parent(3), tree->array[parent(3)]);
printf("Left child of index 1 (%d): index %d (%d)\n",
tree->array[1], leftChild(1), tree->array[leftChild(1)]);
free(tree->array);
free(tree);
return 0;
}
Binary Tree Comparison Table
| Property | Regular Binary Tree | Binary Search Tree | Complete Binary Tree | Full Binary Tree |
|---|---|---|---|---|
| Node values | Any order | Left < Node < Right | Any order | Any order |
| Search complexity | O(n) | O(log n) average | O(n) | O(n) |
| Insert complexity | O(1) at leaf | O(log n) average | O(1) at end | O(1) at leaf |
| Structure constraints | None | Order property | All levels filled except last | Every node has 0 or 2 children |
| Use cases | Expression trees | Dictionary, sets | Heaps, priority queues | Expression trees |
Common Pitfalls
// Pitfall 1: Memory leaks
Node *root = createNode(10);
// ... use tree
// Forgot to freeTree(root) - memory leak!
// Pitfall 2: Not handling NULL properly
void dangerousFunction(Node *root) {
root->data = 42; // Crash if root is NULL!
}
// Correct:
void safeFunction(Node *root) {
if (root != NULL) {
root->data = 42;
}
}
// Pitfall 3: Stack overflow with deep recursion
// For very deep trees (like degenerate BST), recursion may overflow
// Consider iterative solutions for such cases
// Pitfall 4: Modifying tree while traversing
void badTraversal(Node *root) {
if (root) {
badTraversal(root->left);
free(root->left); // Dangerous! Left child already queued
badTraversal(root->right);
}
}
// Pitfall 5: Not considering tree height in algorithm complexity
Best Practices
- Always check for NULL before dereferencing node pointers
- Use appropriate traversal for the task at hand
- Free all memory when done with the tree
- Consider recursion depth for large trees
- Validate BST property after modifications
- Use iterative approaches for tree modifications to avoid recursion overhead
- Document tree properties (BST, balanced, etc.) in comments
Conclusion
Binary trees are fundamental data structures that appear throughout computer science. Key takeaways:
- Each node has at most two children (left and right)
- Traversals (inorder, preorder, postorder, level order) provide different ways to visit nodes
- Binary Search Trees enable efficient searching, insertion, and deletion
- Complete binary trees form the basis for heaps and priority queues
- Tree properties (height, size, balance) are important for analysis
Understanding binary trees is essential for:
- Implementing efficient search structures
- Parsing expressions (compilers)
- Representing hierarchical data
- Understanding more advanced tree structures (AVL, Red-Black, B-trees)
Mastering binary trees provides the foundation for tackling complex algorithms and data structures, making you a more versatile and capable programmer.