1. Binary Tree Categories
Full Binary Tree: A binary tree where all nodes have either 0 or 2 children, and all leaf nodes are at the same level. For depth k, the tree contains (2^k - 1) nodes.
Complete Binary Tree: A binary tree where all levels except possibly the last are completely filled, and all nodes are as far left as possible.
Binary Search Tree (BST): An ordered tree where the left subtree contains only nodes with values less than the root, the right subtree contains only nodes with values greater than the root, and both subtrees are also BSTs.
Balanced Binary Search Tree: Also known as AVL tree, it has the BST property plus the requirement that the height difference between the left and right subtrees of any node is at most 1.
In C++, containers like map, set, multimap, and multiset are implemented using balanced binary search trees (Red-Black trees), giving O(log n) time complexity for insertion and deletion operations.
2. Binary Tree Storage Methods
Linked Storage (Pointer-based): Nodes are stored at arbitrary memory addresses and connected through pointers.
Sequential Storage (Array-based): Elements are stored in contiguous memory locations. For a parent at index i:
- Left child: index 2*i + 1
- Right child: index 2*i + 2
Pointer-based representation is more intuitive for understanding tree structures.
3. Traversal Methods
Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Implemented using recursion or an explicit stack.
- Preorder (Root, Left, Right)
- Inorder (Left, Root, Right)
- Postorder (Left, Right, Root)
Breadth-First Search (BFS): Explores level by level, visiting all nodes at the current depth before moving to the next level. Implemented using a queue.
4. Tree Node Definition
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};
Recursive Traversals
Three Elements of Recursive Algorithms
-
Parameters and Return Value: Identify what data needs to be processed and passed through each recursive call.
-
Base Case: Define when recursion stops. Without proper termination, the call stack will overflow.
-
Recursive Logic: Determine what processing occurs at each level before making the recursive call.
Preorder Traversal
class Solution {
public:
void collectNodes(TreeNode* node, std::vector<int>& result) {
if (node == nullptr) return;
result.push_back(node->value);
collectNodes(node->left, result);
collectNodes(node->right, result);
}
std::vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> result;
collectNodes(root, result);
return result;
}
};
Inorder Traversal
class Solution {
public:
void collectNodes(TreeNode* node, std::vector<int>& result) {
if (node == nullptr) return;
collectNodes(node->left, result);
result.push_back(node->value);
collectNodes(node->right, result);
}
std::vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> result;
collectNodes(root, result);
return result;
}
};
Postorder Traversal
class Solution {
public:
void collectNodes(TreeNode* node, std::vector<int>& result) {
if (node == nullptr) return;
collectNodes(node->left, result);
collectNodes(node->right, result);
result.push_back(node->value);
}
std::vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> result;
collectNodes(root, result);
return result;
}
};
Iterative Traversals
The stack data structure serves as the underlying mechanism for recursive calls.
Preorder Traversal
class Solution {
public:
std::vector<int> preorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
std::vector<int> result;
if (root != nullptr) stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
result.push_back(node->value);
if (node->right != nullptr) stack.push(node->right);
if (node->left != nullptr) stack.push(node->left);
}
return result;
}
};
Key points:
- Never push null nodes onto the stack
- Push right child before left child to ensure left subtree is processed first (LIFO)
- This produces root-left-right ordering
Postorder Traversal
class Solution {
public:
std::vector<int> postorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
std::vector<int> result;
if (root != nullptr) stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
result.push_back(node->value);
if (node->left != nullptr) stack.push(node->left);
if (node->right != nullptr) stack.push(node->right);
}
std::reverse(result.begin(), result.end());
return result;
}
};
By reversing the preorder result (root-right-left becomes left-right-root), we obtain the postorder sequence.
Enorder Traversal
class Solution {
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
std::vector<int> result;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
if (current != nullptr) {
stack.push(current);
current = current->left;
} else {
current = stack.top();
stack.pop();
result.push_back(current->value);
current = current->right;
}
}
return result;
}
};
Traverse to the leftmost node, push all ancestors onto the stack, then process and move to the right subtree.
Unified Iterative Approach
This method uses a sentinel null pointer to mark the boundary between processed and unprocessed nodes.
Preorder Traversal
class Solution {
public:
std::vector<int> preorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
std::vector<int> result;
if (root != nullptr) stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
if (node != nullptr) {
stack.pop();
if (node->right) stack.push(node->right);
if (node->left) stack.push(node->left);
stack.push(node);
stack.push(nullptr);
} else {
stack.pop();
node = stack.top();
result.push_back(node->value);
stack.pop();
}
}
return result;
}
};
Inorder Traversal
class Solution {
public:
std::vector<int> inorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
std::vector<int> result;
if (root != nullptr) stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
if (node != nullptr) {
stack.pop();
if (node->right) stack.push(node->right);
stack.push(node);
stack.push(nullptr);
if (node->left) stack.push(node->left);
} else {
stack.pop();
node = stack.top();
result.push_back(node->value);
stack.pop();
}
}
return result;
}
};
Postorder Traversal
class Solution {
public:
std::vector<int> postorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
std::vector<int> result;
if (root != nullptr) stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
if (node != nullptr) {
stack.pop();
stack.push(node);
stack.push(nullptr);
if (node->right) stack.push(node->right);
if (node->left) stack.push(node->left);
} else {
stack.pop();
node = stack.top();
result.push_back(node->value);
stack.pop();
}
}
return result;
}
};
Level Order Traversal
BFS traverses level by level using a queue data structure.
Level Order - Queue Approach
class Solution {
public:
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::queue<TreeNode*> queue;
std::vector<std::vector<int>> result;
if (root != nullptr) queue.push(root);
while (!queue.empty()) {
int levelSize = queue.size();
std::vector<int> level;
while (levelSize--) {
TreeNode* node = queue.front();
queue.pop();
level.push_back(node->value);
if (node->left) queue.push(node->left);
if (node->right) queue.push(node->right);
}
result.push_back(level);
}
return result;
}
};
Process one level at a time by tracking the queue size before processing each level.
Level Order - Recursive Approach
class Solution {
public:
void collectByLevel(TreeNode* node, std::vector<std::vector<int>>& result, int depth) {
if (node == nullptr) return;
if (result.size() == depth) result.push_back(std::vector<int>());
result[depth].push_back(node->value);
collectByLevel(node->left, result, depth + 1);
collectByLevel(node->right, result, depth + 1);
}
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
collectByLevel(root, result, 0);
return result;
}
};