This guide covers fundamental concepts, traversal methods, and common algorithmic patterns for binary trees, along with related data structures and problem-solving techniques.

Core Binary Tree Concepts

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child.

Key Terminology:

• Root Node: The topmost node in the tree.
• Leaf Node: A node with no children.
• Internal/Branch Node: A node with at least one child.
• Parent/Child: The direct relationship between connected nodes.
• Degree: The number of children a node has.
• Depth: The number of edges from the root to a specific node.
• Height: The number of edges from a specific node to the deepest leaf in its subtree. The height of the root node equals the tree's maximum depth.

Tree Variants:

• N-ary Tree: A generalization where nodes can have up to N children.
• Full Binary Tree: Every node has either 0 or 2 children.
• Complete Binary Tree: All levels are completely filled except possibly the last, which is filled from left to right.
• Balanced Binary Tree: The height difference between the left and right subtrees of any node is at most 1.
• Binary Search Tree (BST): An ordered tree where for any node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

Storage Structures:

• Sequential (Array): For a node at index i, its left child is at 2*i + 1 and its right child at 2*i + 2. Its parent is at index (i-1)/2 (using integer division). Efficient for complete trees.
• Linked (Node-based): Each node contains data and pointers/references to its left and right children. More flexible for general trees.

Related Data Structures:

• Red-Black Tree: A self-balancing BST. Used to implement map, set, multimap, multiset in C++.
• Hash Table: Used to implement unordered_map and unordered_set.
• Priority Queue: Often implemented using a heap (a tree-like structure) over a vector.
• Container Adapters: stack, queue, priority_queue.

Tree Traversal Algorithms

Traversal is the process of visiting all nodes in a tree systematically.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. The order of processing the current node relative to its children defines the type.

Recursive Implementation: The logic is straightforward, following the defined order.

Iterative Implementation (Unified Marking Method): Simulates the recursion call stack. Nodes to be processed are pushed onto a stack along with a marker (like a nullptr) to indicate when processing should occur.

// Example: Iterative Inorder Traversal
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> nodeStack;
    if (root) nodeStack.push(root);

    while (!nodeStack.empty()) {
        TreeNode* currentNode = nodeStack.top();
        nodeStack.pop();
        if (currentNode != nullptr) {
            // Push right, then node with marker, then left (Reverse of process order)
            if (currentNode->right) nodeStack.push(currentNode->right);
            nodeStack.push(currentNode);
            nodeStack.push(nullptr); // Marker
            if (currentNode->left) nodeStack.push(currentNode->left);
        } else {
            // Encounter marker, process the next node
            currentNode = nodeStack.top();
            nodeStack.pop();
            result.push_back(currentNode->val);
        }
    }
    return result;
}

Orders:

• Preorder (NLR): Process current node, then left subtree, then right subtree.
• Inorder (LNR): Process left subtree, then current node, then right subtree. For BST, this yields sorted values.
• Postorder (LRN): Process left subtree, then right subtree, then current node.

Breadth-First Search (BFS) / Level Order Traversal

BFS visits nodes level by level, using a queue.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> levels;
    if (!root) return levels;
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);

    while (!nodeQueue.empty()) {
        int levelSize = nodeQueue.size();
        vector<int> currentLevel;
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = nodeQueue.front();
            nodeQueue.pop();
            currentLevel.push_back(node->val);
            if (node->left) nodeQueue.push(node->left);
            if (node->right) nodeQueue.push(node->right);
        }
        levels.push_back(currentLevel);
    }
    return levels;
}

Common Binary Tree Problems & Patterns

1. Invert (Mirror) a Binary Tree

Swap the left and right child for every node.

Recursive Solution:

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    // Swap children
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    // Recurse
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

Note: For inorder traversal, special care is needed because the left subtree is swapped before processing, so the original right subtree (now left) gets processed next.

2. Maximum and Minimum Depth

• Maximum Depth: Height of the root. Use postorder traversal.
• Minimum Depth: Distance from root to nearest leaf node. A leaf has both children as nullptr.

int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1; // Leaf
    int leftDepth = root->left ? minDepth(root->left) : INT_MAX;
    int rightDepth = root->right ? minDepth(root->right) : INT_MAX;
    return 1 + min(leftDepth, rightDepth);
}

3. Count Nodes in a Complete Binary Tree

Leverage the property of complete trees.

int countCompleteTreeNodes(TreeNode* root) {
    if (!root) return 0;
    int leftHeight = 0, rightHeight = 0;
    TreeNode* leftSubtree = root;
    TreeNode* rightSubtree = root;
    while (leftSubtree) { leftHeight++; leftSubtree = leftSubtree->left; }
    while (rightSubtree) { rightHeight++; rightSubtree = rightSubtree->right; }
    if (leftHeight == rightHeight) {
        // It's a full subtree. Node count = 2^height - 1.
        return (1 << leftHeight) - 1; // 2^leftHeight - 1
    }
    // Otherwise, count recursively
    return 1 + countCompleteTreeNodes(root->left) + countCompleteTreeNodes(root->right);
}

4. Validate a Binary Search Tree

Key Insight: An inorder traversal of a valid BST must produce a strictly increasing sequence.

Recursive (Inorder with Pointer):

class BSTValidator {
private:
    TreeNode* prevNode = nullptr;
public:
    bool isValidBST(TreeNode* root) {
        return validate(root);
    }
    bool validate(TreeNode* node) {
        if (!node) return true;
        // Check left subtree
        if (!validate(node->left)) return false;
        // Check current node: must be > previous node in inorder
        if (prevNode && node->val <= prevNode->val) return false;
        prevNode = node;
        // Check right subtree
        return validate(node->right);
    }
};

5. Lowest Common Ancestor (LCA)

The deepest node that is an ancestor of two given nodes.

General Binary Tree (Postorder):

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
    TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
    if (leftLCA && rightLCA) return root; // p and q are in different subtrees
    return leftLCA ? leftLCA : rightLCA; // Both in one subtree
}

BST (Utilizing Order):

TreeNode* lowestCommonAncestorBST(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return nullptr;
    if (p->val < root->val && q->val < root->val)
        return lowestCommonAncestorBST(root->left, p, q);
    if (p->val > root->val && q->val > root->val)
        return lowestCommonAncestorBST(root->right, p, q);
    return root; // p and q are on different sides, or root is one of them
}

6. Path Sum & All Paths

Path Sum (Check Existence):

bool hasPathSum(TreeNode* root, int target) {
    if (!root) return false;
    // Check if it's a leaf and sum matches
    if (!root->left && !root->right && root->val == target) return true;
    int newTarget = target - root->val;
    return hasPathSum(root->left, newTarget) || hasPathSum(root->right, newTarget);
}

Find All Paths (Backtracking):

void findAllPaths(TreeNode* node, vector<int>& currentPath, vector<vector<int>>& allPaths) {
    if (!node) return;
    currentPath.push_back(node->val);
    // If leaf, save the path
    if (!node->left && !node->right) {
        allPaths.push_back(currentPath);
    } else {
        findAllPaths(node->left, currentPath, allPaths);
        findAllPaths(node->right, currentPath, allPaths);
    }
    currentPath.pop_back(); // Backtrack
}

Constructing Trees from Traversal Sequences

A unique tree can be constructed given inorder combined with either preorder or postorder.

Preorder + Inorder:

TreeNode* buildFromPreIn(vector<int>& preorder, int preStart, int preEnd,
                         vector<int>& inorder, int inStart, int inEnd,
                         unordered_map<int, int>& inorderIndex) {
    if (preStart > preEnd || inStart > inEnd) return nullptr;
    // Root is the first element in preorder segment
    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);
    // Find root's position in inorder
    int rootPosInInorder = inorderIndex[rootVal];
    int leftSubtreeSize = rootPosInInorder - inStart;
    // Recursively build left and right subtrees
    root->left = buildFromPreIn(preorder, preStart + 1, preStart + leftSubtreeSize,
                                inorder, inStart, rootPosInInorder - 1, inorderIndex);
    root->right = buildFromPreIn(preorder, preStart + leftSubtreeSize + 1, preEnd,
                                 inorder, rootPosInInorder + 1, inEnd, inorderIndex);
    return root;
}

Binary Search Tree Operasions

Search

TreeNode* searchBST(TreeNode* root, int target) {
    while (root) {
        if (root->val == target) return root;
        root = (target < root->val) ? root->left : root->right;
    }
    return nullptr;
}

Insertion

TreeNode* insertIntoBST(TreeNode* root, int value) {
    if (!root) return new TreeNode(value);
    if (value < root->val)
        root->left = insertIntoBST(root->left, value);
    else if (value > root->val)
        root->right = insertIntoBST(root->right, value);
    // If value == root->val, handle as per requirements (ignore or insert)
    return root;
}

Deletion

More complex, with three cases:

1. Node is a leaf: Simply remove it.
2. Node has one child: Replace node with its child.
3. Node has two children: Find the inorder successor (smallest in right subtree) or predecessor (largest in left subtree), replace node's value, and recursively delete the successor/predecessor.

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Found the node to delete
        // Case 1 & 2: Zero or one child
        if (!root->left) {
            TreeNode* rightChild = root->right;
            delete root; // Free memory
            return rightChild;
        } else if (!root->right) {
            TreeNode* leftChild = root->left;
            delete root;
            return leftChild;
        }
        // Case 3: Two children
        // Find inorder successor (min in right subtree)
        TreeNode* successor = root->right;
        while (successor->left) successor = successor->left;
        // Replace value
        root->val = successor->val;
        // Delete the successor node from the right subtree
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

Algorithmic Patterns in Tree Problems

The "Two Pointers" Technique in BST

Often used during inorder traversal to compare consecutive nodes (like prev and curr) to find minimum difference, validate BST, or find modes.

Backtracking for Path Problems

Used when you need to explore all path and record them. The key is to add the node before recursion and remove (backtrack) after.

Divide and Conquer for Construction

Tree construcsion problems naturally break down: identify the root, then recursively build left and right subtrees from partitioned sequences.

Performance Notes

• Recursion vs. Iteration: Time complexity is often similar (O(N)), but recursion uses implicit call stack space (O(H) where H is height), which can lead to stack overflow for very deep trees. Iteration with an explicit stack manages this manually.
• BST Operations: Search, insertion, deletion average O(log N) in a balanced BST, degrading to O(N) in a skewed tree.
• Space for Traversal: O(N) for storing results, O(H) for recursion stack or auxiliary traversal stack/queue.