Trees
Trees are hierarchical data structures consisting of nodes connected by edges. Each tree has a root node and zero or more subtrees. Trees are fundamental in computer science and are used for organizing data, searching, sorting, and representing hierarchical relationships.
Common applications include file systems, expression parsing, decision trees, and database indexing. Binary trees, in particular, form the foundation for many efficient algorithms.
Binary Tree Basics
A binary tree is a tree where each node has at most two children, typically called left and right child:
Binary Tree Implementation
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BinaryTree {
private:
TreeNode* root;
// Helper function for inorder traversal
void inorderHelper(TreeNode* node) {
if (node != nullptr) {
inorderHelper(node->left);
cout << node->data << " ";
inorderHelper(node->right);
}
}
// Helper function for preorder traversal
void preorderHelper(TreeNode* node) {
if (node != nullptr) {
cout << node->data << " ";
preorderHelper(node->left);
preorderHelper(node->right);
}
}
// Helper function for postorder traversal
void postorderHelper(TreeNode* node) {
if (node != nullptr) {
postorderHelper(node->left);
postorderHelper(node->right);
cout << node->data << " ";
}
}
// Helper function to calculate height
int heightHelper(TreeNode* node) {
if (node == nullptr) return -1;
return 1 + max(heightHelper(node->left), heightHelper(node->right));
}
// Helper function to delete tree
void deleteTree(TreeNode* node) {
if (node != nullptr) {
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
public:
BinaryTree() : root(nullptr) {}
~BinaryTree() {
deleteTree(root);
}
// Insert using level-order (breadth-first)
void insert(int value) {
TreeNode* newNode = new TreeNode(value);
if (root == nullptr) {
root = newNode;
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
if (current->left == nullptr) {
current->left = newNode;
return;
} else if (current->right == nullptr) {
current->right = newNode;
return;
} else {
q.push(current->left);
q.push(current->right);
}
}
}
// Tree traversals
void inorderTraversal() {
cout << "Inorder: ";
inorderHelper(root);
cout << endl;
}
void preorderTraversal() {
cout << "Preorder: ";
preorderHelper(root);
cout << endl;
}
void postorderTraversal() {
cout << "Postorder: ";
postorderHelper(root);
cout << endl;
}
// Level-order traversal (breadth-first)
void levelOrderTraversal() {
if (root == nullptr) return;
cout << "Level-order: ";
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
cout << current->data << " ";
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
cout << endl;
}
int height() {
return heightHelper(root);
}
};
int main() {
BinaryTree tree;
// Insert nodes
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
cout << "Tree traversals:" << endl;
tree.inorderTraversal();
tree.preorderTraversal();
tree.postorderTraversal();
tree.levelOrderTraversal();
cout << "Tree height: " << tree.height() << endl;
return 0;
}Binary Search Tree (BST)
A Binary Search Tree is a binary tree where the left subtree contains nodes with values less than the root, and the right subtree contains nodes with values greater than the root:
Binary Search Tree Implementation
#include <iostream>
using namespace std;
struct BSTNode {
int data;
BSTNode* left;
BSTNode* right;
BSTNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BST {
private:
BSTNode* root;
BSTNode* insertHelper(BSTNode* node, int value) {
if (node == nullptr) {
return new BSTNode(value);
}
if (value < node->data) {
node->left = insertHelper(node->left, value);
} else if (value > node->data) {
node->right = insertHelper(node->right, value);
}
// If value equals node->data, we don't insert (no duplicates)
return node;
}
BSTNode* searchHelper(BSTNode* node, int value) {
if (node == nullptr || node->data == value) {
return node;
}
if (value < node->data) {
return searchHelper(node->left, value);
} else {
return searchHelper(node->right, value);
}
}
BSTNode* findMin(BSTNode* node) {
while (node && node->left) {
node = node->left;
}
return node;
}
BSTNode* deleteHelper(BSTNode* node, int value) {
if (node == nullptr) return node;
if (value < node->data) {
node->left = deleteHelper(node->left, value);
} else if (value > node->data) {
node->right = deleteHelper(node->right, value);
} else {
// Node to be deleted found
if (node->left == nullptr) {
BSTNode* temp = node->right;
delete node;
return temp;
} else if (node->right == nullptr) {
BSTNode* temp = node->left;
delete node;
return temp;
}
// Node with two children
BSTNode* temp = findMin(node->right);
node->data = temp->data;
node->right = deleteHelper(node->right, temp->data);
}
return node;
}
void inorderHelper(BSTNode* node) {
if (node != nullptr) {
inorderHelper(node->left);
cout << node->data << " ";
inorderHelper(node->right);
}
}
void deleteTree(BSTNode* node) {
if (node != nullptr) {
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
}
public:
BST() : root(nullptr) {}
~BST() {
deleteTree(root);
}
void insert(int value) {
root = insertHelper(root, value);
}
bool search(int value) {
return searchHelper(root, value) != nullptr;
}
void remove(int value) {
root = deleteHelper(root, value);
}
void inorderTraversal() {
cout << "BST (sorted): ";
inorderHelper(root);
cout << endl;
}
};
int main() {
BST bst;
// Insert values
int values[] = {50, 30, 70, 20, 40, 60, 80};
for (int val : values) {
bst.insert(val);
}
bst.inorderTraversal(); // Should print in sorted order
// Search
cout << "Search 40: " << (bst.search(40) ? "Found" : "Not Found") << endl;
cout << "Search 25: " << (bst.search(25) ? "Found" : "Not Found") << endl;
// Delete
bst.remove(30);
cout << "After deleting 30: ";
bst.inorderTraversal();
return 0;
}Tree Applications
Expression Tree
Expression trees represent mathematical expressions where operators are internal nodes and operands are leaves:
Expression Tree Evaluation
#include <iostream>
#include <stack>
#include <string>
using namespace std;
struct ExprNode {
string data;
ExprNode* left;
ExprNode* right;
ExprNode(string value) : data(value), left(nullptr), right(nullptr) {}
};
class ExpressionTree {
private:
ExprNode* root;
bool isOperator(string str) {
return str == "+" || str == "-" || str == "*" || str == "/";
}
int evaluate(ExprNode* node) {
if (node == nullptr) return 0;
// If leaf node (operand)
if (!isOperator(node->data)) {
return stoi(node->data);
}
// Evaluate left and right subtrees
int leftVal = evaluate(node->left);
int rightVal = evaluate(node->right);
// Apply operator
if (node->data == "+") return leftVal + rightVal;
if (node->data == "-") return leftVal - rightVal;
if (node->data == "*") return leftVal * rightVal;
if (node->data == "/") return leftVal / rightVal;
return 0;
}
void inorderHelper(ExprNode* node) {
if (node != nullptr) {
if (isOperator(node->data)) cout << "(";
inorderHelper(node->left);
cout << node->data;
inorderHelper(node->right);
if (isOperator(node->data)) cout << ")";
}
}
public:
ExpressionTree() : root(nullptr) {}
// Build expression tree from postfix expression
void buildFromPostfix(vector<string> postfix) {
stack<ExprNode*> st;
for (string token : postfix) {
ExprNode* node = new ExprNode(token);
if (isOperator(token)) {
node->right = st.top(); st.pop();
node->left = st.top(); st.pop();
}
st.push(node);
}
root = st.top();
}
int evaluateExpression() {
return evaluate(root);
}
void printInfix() {
cout << "Infix expression: ";
inorderHelper(root);
cout << endl;
}
};
int main() {
ExpressionTree tree;
// Postfix expression: "2 3 + 4 *" represents (2 + 3) * 4
vector<string> postfix = {"2", "3", "+", "4", "*"};
tree.buildFromPostfix(postfix);
tree.printInfix();
cout << "Result: " << tree.evaluateExpression() << endl;
// Another example: "15 7 1 1 + - / 3 * 2 1 1 + + -"
vector<string> complex = {"15", "7", "1", "1", "+", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"};
ExpressionTree complexTree;
complexTree.buildFromPostfix(complex);
complexTree.printInfix();
cout << "Result: " << complexTree.evaluateExpression() << endl;
return 0;
}