PROBLEM SOLVING - TREE TRICKS

Tree Manipulation Approaches

#	Technique	Use Case	Approach	Complexity	Examples
1	Tree Traversals	Processing all nodes in specific order	Recursive or iterative approaches (DFS/BFS)	O(n)	In-order traversal Level-order traversal Zigzag traversal Boundary traversal
2	BST Operations	Search, insert, delete in BST	Leverage BST property (left < root < right)	O(h)	Search in BST Delete node from BST Validate BST
3	Tree Construction	Build tree from traversal data	Use recursion with traversal sequences	O(n)	Build from in+pre order Build from in+post order Serialize/deserialize
4	Tree Properties	Calculate tree characteristics	Recursive traversal with property checks	O(n)	Height/depth of tree Check balanced tree Count nodes/leaves
5	Path Sum	Find paths with specific sums	DFS with backtracking to track paths	O(n)	Path sum exists All path sums Maximum path sum
6	LCA	Find common ancestor of two nodes	Recursive search or parent pointer traversal	O(n)	LCA in binary tree LCA in BST Distance between nodes
7	Tree Views	Get specific views of the tree	Modified BFS/DFS with tracking	O(n)	Left/right view Top/bottom view Diagonal view
8	Tree Modification	Modify tree structure	Recursive traversal with structural changes	O(n) time O(h) space	Mirror tree Flatten tree Prune tree

Common Tree Operations

Tree Height

int height(struct Node* node) {
    if (node == NULL) return 0;
    int left = height(node->left);
    int right = height(node->right);
    return 1 + max(left, right);
}

Time Complexity: O(n)

Count Nodes

int countNodes(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) 
             + countNodes(root->right);
}

Time Complexity: O(n)

Search in BST

struct Node* searchBST(struct Node* root, int val) {
    if (root == NULL || root->data == val)
        return root;
    if (val < root->data)
        return searchBST(root->left, val);
    return searchBST(root->right, val);
}

Time Complexity: O(h)

Check Balanced Tree

int isBalanced(struct Node* root) {
    if (root == NULL) return 1;
    int lh = height(root->left);
    int rh = height(root->right);
    return abs(lh - rh) <= 1 && 
           isBalanced(root->left) && 
           isBalanced(root->right);
}

Time Complexity: O(n²)

Invert Binary Tree

struct Node* invertTree(struct Node* root) {
    if (root == NULL) return NULL;
    struct Node* left = invertTree(root->left);
    struct Node* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

Time Complexity: O(n)

Level Order Traversal

void levelOrder(struct Node* root) {
    if (root == NULL) return;
    queue<struct Node*> q;
    q.push(root);
    while (!q.empty()) {
        struct Node* node = q.front();
        q.pop();
        printf("%d ", node->data);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

Time Complexity: O(n)

Advanced Tree Techniques

#	Technique	Description	Use Case
1	AVL Trees	Self-balancing binary search tree with height difference ≤ 1	Balanced search operations
2	Red-Black Trees	Self-balancing BST with color properties for balancing	Efficient insert/delete operations
3	Trie	Prefix tree for efficient string storage and retrieval	Autocomplete, dictionary
4	Segment Trees	Tree for storing intervals or segments for range queries	Range sum/min/max queries
5	Fenwick Trees	Binary indexed tree for efficient prefix sum calculations	Dynamic prefix sums
6	B-Trees	Self-balancing tree with multiple children per node	Database indexing
7	Tree Isomorphism	Check if two trees have identical structure	Tree comparison
8	Euler Tour	Traversal that visits each edge exactly twice	Subtree queries, LCA
9	Heavy-Light Decomposition	Decomposes tree into chains for efficient path queries	Path operations
10	Binary Lifting	Technique for efficient ancestor queries in trees	LCA, k-th ancestor

Related Tree Resources

Linkedlist Programs

Stack Interview Questions

Queue MCQs

Tech Hub