Essential Binary Tree Variations For Coding Interviews
sai ganesh reddy
1367
GoogleLeetCodeBinary TreePlacementCareerDSAInterviewThe LeetCode Beginner's Guide

Hey everyone! Binary trees are one of the most frequently asked topics in coding interviews, yet many of us struggle because we try to memorize solutions instead of understanding patterns. Once you recognize these patterns, tree problems become straightforward. So I've compiled this complete guide to binary tree variations with templates and must-solve problems!

Variation 1: Tree Traversals

Why this matters:
Every tree problem uses traversal. Master these first, everything else builds on them.

Types:

  1. Inorder (Left → Root → Right) - BST sorted order
  2. Preorder (Root → Left → Right) - Tree copying, serialization
  3. Postorder (Left → Right → Root) - Tree deletion, bottom-up problems
  4. Level-order (BFS) - Shortest path, level-wise operations

Practice Problems:

  1. Binary Tree Inorder Traversal
  2. Binary Tree Preorder Traversal
  3. Binary Tree Postorder Traversal
  4. Binary Tree Level Order Traversal
  5. Binary Tree Zigzag Level Order Traversal
  6. Binary Tree Level Order Traversal II
  7. Binary Tree Right Side View
  8. Average of Levels in Binary Tree

Variation 2: Tree Properties (Height, Depth, Diameter)

Why this matters:
Many problems boil down to computing tree properties. These are building blocks for complex problems.

Key concepts:

  • Height: Distance from node to deepest leaf
  • Depth: Distance from root to node
  • Diameter: Longest path between any two nodes

Template (Height/Depth):

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    
    return Math.max(leftHeight, rightHeight) + 1;
}

Template (Diameter):

class Solution {
    int diameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }
    
    private int height(TreeNode root) {
        if (root == null) return 0;
        
        int left = height(root.left);
        int right = height(root.right);
        
        // Update diameter
        diameter = Math.max(diameter, left + right);
        
        return Math.max(left, right) + 1;
    }
}

Practice Problems:

  1. Maximum Depth of Binary Tree
  2. Minimum Depth of Binary Tree
  3. Diameter of Binary Tree
  4. Balanced Binary Tree
  5. Count Complete Tree Nodes
  6. Maximum Width of Binary Tree

Variation 3: Tree Comparison (Same, Symmetric, Subtree)

Why this matters:
Testing structural properties and equality is common. Learn to compare trees effectively.

Key patterns:

  • Same tree: Compare structure and values
  • Symmetric: Mirror comparison
  • Subtree: Check if tree is subtree of another

Template (Same Tree):

boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    
    return p.val == q.val 
        && isSameTree(p.left, q.left)
        && isSameTree(p.right, q.right);
}

Template (Symmetric Tree):

boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    
    return t1.val == t2.val
        && isMirror(t1.left, t2.right)
        && isMirror(t1.right, t2.left);
}

Practice Problems:

  1. Same Tree
  2. Symmetric Tree
  3. Subtree of Another Tree
  4. Leaf-Similar Trees
  5. Flip Equivalent Binary Trees

Variation 4: Path Sum Problems

Why this matters:
Path problems teach you to maintain state during recursion. Very common in interviews.

Key patterns:

  • Single path from root to leaf
  • Any path (not necessarily root to leaf)
  • Count paths with target sum
  • Maximum/minimum path sum

Template (Root to Leaf Path Sum):

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    
    // Leaf node
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

Template (Any Path Sum - Two Recursive Calls):

class Solution {
    int count = 0;
    
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        
        // Paths starting from current node
        dfs(root, targetSum);
        
        // Paths in left and right subtrees
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        
        return count;
    }
    
    private void dfs(TreeNode node, long sum) {
        if (node == null) return;
        
        if (node.val == sum) count++;
        
        dfs(node.left, sum - node.val);
        dfs(node.right, sum - node.val);
    }
}

Template (Maximum Path Sum ):

class Solution {
    int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        
        // Max gain from left and right (ignore negative)
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // Path through current node
        int pathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathSum);
        
        // Return max gain if we continue with this node
        return node.val + Math.max(leftGain, rightGain);
    }
}

Practice Problems:

  1. Path Sum
  2. Path Sum II
  3. Path Sum III
  4. Binary Tree Maximum Path Sum
  5. Sum Root to Leaf Numbers
  6. Smallest String Starting From Leaf

Variation 5: Tree Construction

Why this matters:
Building trees from traversals tests your understanding of tree structure deeply.

Key patterns:

  • Build from preorder + inorder
  • Build from postorder + inorder
  • Build from level-order
  • Build from string representation

Template (Preorder + Inorder):

class Solution {
    int preIndex = 0;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return build(preorder, inMap, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] preorder, Map<Integer, Integer> inMap, 
                          int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        
        int inIndex = inMap.get(rootVal);
        
        root.left = build(preorder, inMap, inStart, inIndex - 1);
        root.right = build(preorder, inMap, inIndex + 1, inEnd);
        
        return root;
    }
}

Key insight:

  • Preorder gives root first
  • Inorder splits into left and right subtrees
  • Use hash map for O(1) lookup

Practice Problems:

  1. Construct Binary Tree from Preorder and Inorder Traversal
  2. Construct Binary Tree from Inorder and Postorder Traversal
  3. Construct Binary Tree from Preorder and Postorder Traversal
  4. Maximum Binary Tree
  5. Recover Binary Search Tree

Variation 6: Lowest Common Ancestor (LCA)

Why this matters:
LCA is a fundamental tree operation used in many scenarios - path finding, distance calculation.

Key patterns:

  • LCA in binary tree
  • LCA in BST (can optimize using BST property)
  • LCA with parent pointers

Template (Binary Tree LCA):

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // If both left and right are non-null, root is LCA
    if (left != null && right != null) {
        return root;
    }
    
    // Return non-null child
    return left != null ? left : right;
}

Template (BST LCA - Optimized):

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // Both in left subtree
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    
    // Both in right subtree
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    
    // Split point (or one of them is root)
    return root;
}

Practice Problems:

  1. Lowest Common Ancestor of a Binary Tree
  2. Lowest Common Ancestor of a Binary Search Tree
  3. Lowest Common Ancestor of Deepest Leaves
  4. Lowest Common Ancestor of a Binary Tree II
  5. Lowest Common Ancestor of a Binary Tree III

Variation 7: Binary Search Tree (BST) Operations

Why this matters:
BST properties enable O(log n) operations. Understanding BST is crucial for many optimization problems.

Key properties:

  • Left subtree < Root < Right subtree
  • Inorder traversal gives sorted order
  • Search, insert, delete in O(log n) average

Template (Validate BST):

boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

boolean validate(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    
    if ((min != null && node.val <= min) || 
        (max != null && node.val >= max)) {
        return false;
    }
    
    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
}

Template (Insert into BST):

TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    
    return root;
}

Template (Delete from BST):

TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // Node to delete found
        
        // Case 1: Leaf or one child
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Case 2: Two children
        // Find inorder successor (smallest in right subtree)
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, root.val);
    }
    
    return root;
}

TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

Practice Problems:

  1. Validate Binary Search Tree
  2. Kth Smallest Element in a BST
  3. Insert into a Binary Search Tree
  4. Delete Node in a BST
  5. Convert Sorted Array to Binary Search Tree
  6. Range Sum of BST
  7. Minimum Absolute Difference in BST

Variation 8: Tree Modification

Why this matters:
Many problems require modifying tree structure in place. Tests pointer manipulation skills.

Key patterns:

  • Invert/flip tree
  • Flatten tree to linked list
  • Connect nodes at same level
  • Prune tree

Template (Invert Tree):

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    // Swap children
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    // Recursively invert subtrees
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

Template (Flatten to Linked List):

TreeNode prev = null;

void flatten(TreeNode root) {
    if (root == null) return;
    
    // Post-order traversal (right, left, root)
    flatten(root.right);
    flatten(root.left);
    
    // Connect
    root.right = prev;
    root.left = null;
    prev = root;
}

Template (Connect Level Order Siblings):

Node connect(Node root) {
    if (root == null) return null;
    
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node prev = null;
        
        for (int i = 0; i < size; i++) {
            Node curr = queue.poll();
            
            if (prev != null) {
                prev.next = curr;
            }
            prev = curr;
            
            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }
    }
    
    return root;
}

Practice Problems:

  1. Invert Binary Tree
  2. Flatten Binary Tree to Linked List
  3. Populating Next Right Pointers in Each Node
  4. Populating Next Right Pointers in Each Node II
  5. Binary Tree Pruning
  6. Delete Leaves With a Given Value

Variation 9: Serialization & Deserialization

Why this matters:
Converting trees to/from strings tests deep understanding of tree structure and traversals.

Key patterns:

  • Using preorder with markers for null
  • Using level-order traversal
  • Compact representation

Template (Preorder with Null Markers):

class Codec {
    // Serialize
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("null,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }
    
    // Deserialize
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodes);
    }
    
    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("null")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }
}

Practice Problems:

  1. Serialize and Deserialize Binary Tree
  2. Serialize and Deserialize BST
  3. Encode N-ary Tree to Binary Tree
  4. Construct String from Binary Tree
  5. Find Duplicate Subtrees

Variation 10: Views of Binary Tree

Why this matters:
View problems teach you to think about tree structure from different perspectives.

Types:

  • Left view: Leftmost node at each level
  • Right view: Rightmost node at each level
  • Top view: Nodes visible from top
  • Bottom view: Nodes visible from bottom

Template (Right Side View):

List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            
            // Last node at this level
            if (i == size - 1) {
                result.add(node.val);
            }
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    
    return result;
}

Template (Vertical Order Traversal):

List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Map<Integer, List<Integer>> map = new TreeMap<>();
    Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
    queue.offer(new Pair<>(root, 0));
    
    while (!queue.isEmpty()) {
        Pair<TreeNode, Integer> pair = queue.poll();
        TreeNode node = pair.getKey();
        int col = pair.getValue();
        
        map.putIfAbsent(col, new ArrayList<>());
        map.get(col).add(node.val);
        
        if (node.left != null) {
            queue.offer(new Pair<>(node.left, col - 1));
        }
        if (node.right != null) {
            queue.offer(new Pair<>(node.right, col + 1));
        }
    }
    
    result.addAll(map.values());
    return result;
}

Practice Problems:

  1. Binary Tree Right Side View
  2. Binary Tree Left Side View
  3. Vertical Order Traversal of a Binary Tree
  4. Binary Tree Top View
  5. Binary Tree Bottom View
  6. Boundary of Binary Tree

Variation 11: Morris Traversal

Why this matters:
Morris traversal achieves O(1) space without recursion or stack. Advanced but impressive in interviews.

Key concept:

  • Use threaded binary tree concept
  • Create temporary links to successor
  • Restore tree structure after traversal

Template (Morris Inorder):

List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;
    
    while (curr != null) {
        if (curr.left == null) {
            // No left child, visit and go right
            result.add(curr.val);
            curr = curr.right;
        } else {
            // Find inorder predecessor
            TreeNode pred = curr.left;
            while (pred.right != null && pred.right != curr) {
                pred = pred.right;
            }
            
            if (pred.right == null) {
                // Create thread
                pred.right = curr;
                curr = curr.left;
            } else {
                // Thread exists, visit and remove
                pred.right = null;
                result.add(curr.val);
                curr = curr.right;
            }
        }
    }
    
    return result;
}

Practice Problems:

  1. Binary Tree Inorder Traversal (Morris)
  2. Binary Tree Preorder Traversal (Morris)
  3. Flatten Binary Tree to Linked List (Morris)
  4. Recover Binary Search Tree (Morris)

Variation 12: Special Binary Trees

Why this matters:
Understanding special tree types and their properties helps optimize solutions.

Types:

  • Complete Binary Tree: All levels filled except possibly last (filled left to right)
  • Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
  • Full Binary Tree: Every node has 0 or 2 children
  • Balanced Binary Tree: Left and right subtrees differ by at most 1 in height

Template (Check Complete Binary Tree):

boolean isCompleteTree(TreeNode root) {
    if (root == null) return true;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean seenNull = false;
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        
        if (node == null) {
            seenNull = true;
        } else {
            if (seenNull) return false; // Node after null
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    
    return true;
}

Template (Check Balanced Tree):

boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

int checkHeight(TreeNode node) {
    if (node == null) return 0;
    
    int left = checkHeight(node.left);
    if (left == -1) return -1;
    
    int right = checkHeight(node.right);
    if (right == -1) return -1;
    
    if (Math.abs(left - right) > 1) return -1;
    
    return Math.max(left, right) + 1;
}

Practice Problems:

  1. Balanced Binary Tree
  2. Check Completeness of a Binary Tree
  3. Count Complete Tree Nodes
  4. Find Bottom Left Tree Value
  5. All Possible Full Binary Trees

Complete Problem List

  1. Maximum Depth of Binary Tree
  2. Invert Binary Tree
  3. Same Tree
  4. Symmetric Tree
  5. Path Sum
  6. Balanced Binary Tree
  7. Minimum Depth of Binary Tree
  8. Merge Two Binary Trees
  9. Range Sum of BST
  10. Diameter of Binary Tree
  11. Sum of Left Leaves
  12. Binary Tree Paths
  13. Convert Sorted Array to Binary Search Tree
  14. Subtree of Another Tree
  15. Leaf-Similar Trees
  16. Binary Tree Level Order Traversal
  17. Binary Tree Zigzag Level Order Traversal
  18. Binary Tree Right Side View
  19. Kth Smallest Element in a BST
  20. Validate Binary Search Tree
  21. Lowest Common Ancestor of a Binary Tree
  22. Lowest Common Ancestor of a Binary Search Tree
  23. Construct Binary Tree from Preorder and Inorder Traversal
  24. Construct Binary Tree from Inorder and Postorder Traversal
  25. Flatten Binary Tree to Linked List
  26. Populating Next Right Pointers in Each Node
  27. Binary Tree Maximum Path Sum
  28. Path Sum II
  29. Path Sum III
  30. Sum Root to Leaf Numbers
  31. Count Complete Tree Nodes
  32. Binary Tree Vertical Order Traversal
  33. All Nodes Distance K in Binary Tree
  34. Delete Node in a BST
  35. Insert into a Binary Search Tree
  36. Serialize and Deserialize Binary Tree
  37. Find Duplicate Subtrees
  38. Longest Univalue Path
  39. House Robber III
  40. Binary Tree Pruning
  41. Maximum Width of Binary Tree
  42. Add One Row to Tree
  43. Find Bottom Left Tree Value
  44. Deepest Leaves Sum
  45. Binary Tree Cameras
  46. Binary Tree Maximum Path Sum
  47. Serialize and Deserialize Binary Tree
  48. Binary Tree Postorder Traversal (Iterative)
  49. Recover Binary Search Tree
  50. Vertical Order Traversal of a Binary Tree
  51. Binary Tree Cameras
  52. Distribute Coins in Binary Tree
  53. Maximum Sum BST in Binary Tree
  54. Count of Smaller Numbers After Self
  55. Closest Binary Search Tree Value II

Check out my posts which may help you in your preparation :

  1. 13 DP Patterns for Interview Preparation
  2. 10 Dijkstra Variations for Interview Preparation
  3. Understanding Time Complexity: The 10^8 Operations Rule
  4. 10 Essential Design Problems for DSA Interviews
  5. Essential CS Fundamental Topics For Interviews
  6. Essential Graph Patterns for Coding Interviews
  7. Essential String Patterns for Coding Interviews
  8. 15 Essential DSA Patterns for Tech Interviews
  9. The 10 Variations of Two Pointers for Interview Preparation

Which tree variation do you find most challenging? Or do you have a favorite tree problem? Let's discuss! 👇

Comments (3)