Essential Binary Tree Variations For Coding Interviews

1596

Nov 15, 2025

Nov 17, 2025

Google LeetCode Binary Tree Placement Career DSA Interview The 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:

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

Practice Problems:

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:

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:

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:

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:

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:

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:

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:

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:

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:

Binary Tree Right Side View
Binary Tree Left Side View
Vertical Order Traversal of a Binary Tree
Binary Tree Top View
Binary Tree Bottom View
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:

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:

Complete Problem List

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

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

Comments (3)

Essential Binary Tree Variations For Coding Interviews

Variation 1: Tree Traversals

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

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

Variation 4: Path Sum Problems

Variation 5: Tree Construction

Variation 6: Lowest Common Ancestor (LCA)

Variation 7: Binary Search Tree (BST) Operations

Variation 8: Tree Modification

Variation 9: Serialization & Deserialization

Variation 10: Views of Binary Tree

Variation 11: Morris Traversal

Variation 12: Special Binary Trees

Complete Problem List

Related Posts