Loading W Code...
Hierarchical data structure - Binary Trees, BST, Traversals and more.
4
Topics
50
Minutes
C++
Language
Key Terminology:
- Root: Topmost node (no parent)
- Parent: Node that has children
- Child: Node connected below a parent
- Leaf: Node with no children
- Height: Longest path from root to leaf
- Depth: Distance from root to a node
- Subtree: Tree formed by a node and its descendants
Real-life examples:
- Family tree (ancestors/descendants)
- File system (folders/files)
- Organization hierarchy (CEO → Managers → Employees)
- HTML DOM structure
Why Trees?
- Efficient searching (Binary Search Tree)
- Hierarchical data representation
- Decision making (Decision Trees)
#include <iostream>
using namespace std;
// Basic Tree Node
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
int main() {
// Create a simple binary tree
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << "Root: " << root->data << endl;
cout << "Left child: " << root->left->data << endl;
cout << "Right child: " << root->right->data << endl;
return 0;
}Types of Binary Trees:
1. Full Binary Tree: Every node has 0 or 2 children
2. Complete Binary Tree: All levels filled except possibly last (filled left to right)
3. Perfect Binary Tree: All leaves at same level, every node has 2 children
4. Balanced Binary Tree: Height difference between left and right subtrees ≤ 1
Binary Search Tree (BST):
Special binary tree with ordering property:
- Left subtree contains nodes with values less than parent
- Right subtree contains nodes with values greater than parent
- This property holds for ALL nodes
BST Advantage:
Search, Insert, Delete: O(log n) average case (O(n) worst case for skewed tree)
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class BST {
public:
TreeNode* root;
BST() : root(nullptr) {}
// Insert into BST
TreeNode* insert(TreeNode* node, int val) {
if (node == nullptr) {
return new TreeNode(val);
}
if (val < node->data) {
node->left = insert(node->left, val);
} else {
node->right = insert(node->right, val);
}
return node;
}
void insert(int val) {
root = insert(root, val);
}
// Search in BST
bool search(TreeNode* node, int val) {
if (node == nullptr) return false;
if (node->data == val) return true;
if (val < node->data) {
return search(node->left, val);
} else {
return search(node->right, val);
}
}
bool search(int val) {
return search(root, val);
}
// Inorder traversal (gives sorted order for BST)
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
};
int main() {
BST tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
cout << "Inorder (sorted): ";
tree.inorder(tree.root);
cout << endl; // 20 30 40 50 70
cout << "Search 40: " << (tree.search(40) ? "Found" : "Not Found") << endl;
cout << "Search 100: " << (tree.search(100) ? "Found" : "Not Found") << endl;
return 0;
}1. Inorder (Left → Root → Right)
- For BST, gives nodes in sorted order
- Used for: Getting sorted elements
2. Preorder (Root → Left → Right)
- Root is visited first
- Used for: Creating copy of tree, prefix expressions
3. Postorder (Left → Right → Root)
- Root is visited last
- Used for: Deleting tree, postfix expressions
4. Level Order (BFS)
- Visit level by level, left to right
- Uses Queue
- Used for: Finding shortest path, level-wise processing
Memory Tip:
- Pre = Root first
- Post = Root last
- In = Root in middle
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Inorder: Left -> Root -> Right
void inorder(TreeNode* node) {
if (node == nullptr) return;
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
// Preorder: Root -> Left -> Right
void preorder(TreeNode* node) {
if (node == nullptr) return;
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
// Postorder: Left -> Right -> Root
void postorder(TreeNode* node) {
if (node == nullptr) return;
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
// Level Order (BFS)
void levelOrder(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->data << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
int main() {
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << "Inorder: "; inorder(root); cout << endl; // 4 2 5 1 3
cout << "Preorder: "; preorder(root); cout << endl; // 1 2 4 5 3
cout << "Postorder: "; postorder(root); cout << endl; // 4 5 2 3 1
cout << "Level Order: "; levelOrder(root); cout << endl; // 1 2 3 4 5
return 0;
}Depth of a Node:
Number of edges from root to that node.
- Depth of root = 0
Diameter of Tree:
The longest path between any two nodes (may or may not pass through root).
Common Interview Problems:
1. Find height of tree
2. Check if tree is balanced
3. Find diameter
4. Find maximum/minimum depth
5. Count nodes at each level
#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Height of tree
int height(TreeNode* node) {
if (node == nullptr) return -1; // or 0 depending on definition
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return 1 + max(leftHeight, rightHeight);
}
// Check if balanced (height diff <= 1 for all nodes)
int checkBalance(TreeNode* node, bool& balanced) {
if (node == nullptr) return -1;
int leftH = checkBalance(node->left, balanced);
int rightH = checkBalance(node->right, balanced);
if (abs(leftH - rightH) > 1) {
balanced = false;
}
return 1 + max(leftH, rightH);
}
bool isBalanced(TreeNode* root) {
bool balanced = true;
checkBalance(root, balanced);
return balanced;
}
// Diameter of tree (optimized - O(n))
int diameterHelper(TreeNode* node, int& diameter) {
if (node == nullptr) return 0;
int leftH = diameterHelper(node->left, diameter);
int rightH = diameterHelper(node->right, diameter);
// Update diameter if path through this node is longer
diameter = max(diameter, leftH + rightH);
return 1 + max(leftH, rightH);
}
int diameter(TreeNode* root) {
int dia = 0;
diameterHelper(root, dia);
return dia;
}
int main() {
// 1
// / \
// 2 3
// / \
// 4 5
// /
// 6
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->left->left->left = new TreeNode(6);
cout << "Height: " << height(root) << endl; // 3
cout << "Balanced: " << (isBalanced(root) ? "Yes" : "No") << endl; // No
cout << "Diameter: " << diameter(root) << endl; // 4 (path: 6-4-2-5 or 6-4-2-1-3)
return 0;
}