Trees Cheatsheet

REFERENCE v1.0

Trees Quick Reference

Everything you need day‑to‑day – traversals, operations, and algorithms.

Tree Basics

Terminology

Root – topmost node
Parent – node above
Child – node below
Leaf – no children
Internal node – has children
Depth – edges from root
Height – longest path to leaf
Subtree – node and descendants

Tree Types

Binary Tree – ≤ 2 children
Binary Search Tree – left < parent < right
AVL Tree – self‑balancing BST
Red‑Black Tree – balanced BST
B‑Tree – balanced multi‑way
Heap – priority tree
Trie – prefix tree
N‑ary Tree – ≤ N children

Node Structure

Binary Tree Node

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

N‑ary Tree Node

class TreeNode {
    int val;
    List<TreeNode> children;
    TreeNode(int val) { this.val = val; }
}

Tree Traversals

Depth‑First Search (DFS)

Pre‑order (Root, Left, Right)

void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

In‑order (Left, Root, Right)

void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

Post‑order (Left, Right, Root)

void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

Iterative Pre‑order (Stack)

void preorderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        System.out.print(curr.val + " ");
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }
}

Breadth‑First Search (BFS) / Level Order

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode curr = q.poll();
        System.out.print(curr.val + " ");
        if (curr.left != null) q.offer(curr.left);
        if (curr.right != null) q.offer(curr.right);
    }
}

// Level order with levels
List<List<Integer>> levelOrderList(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();
            level.add(curr.val);
            if (curr.left != null) q.offer(curr.left);
            if (curr.right != null) q.offer(curr.right);
        }
        result.add(level);
    }
    return result;
}

Binary Search Tree (BST)

Search

TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return search(root.left, target);
    return search(root.right, target);
}

Insert

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

Delete

TreeNode delete(TreeNode root, int val) {
    if (root == null) return null;
    if (val < root.val) root.left = delete(root.left, val);
    else if (val > root.val) root.right = delete(root.right, val);
    else {
        // Leaf or one child
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // Two children – find inorder successor (min in right subtree)
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = delete(root.right, minNode.val);
    }
    return root;
}

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

Find Min / Max

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

TreeNode findMax(TreeNode root) {
    if (root == null) return null;
    while (root.right != null) root = root.right;
    return root;
}

Validate BST

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

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

Tree Algorithms

Height / Depth

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

Diameter

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

Lowest Common Ancestor (BST)

TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root.val > Math.max(p.val, q.val))
        return LCA(root.left, p, q);
    if (root.val < Math.min(p.val, q.val))
        return LCA(root.right, p, q);
    return root;
}

Lowest Common Ancestor (Binary Tree)

TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = LCA(root.left, p, q);
    TreeNode right = LCA(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Check Balanced

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

Invert Tree

TreeNode invert(TreeNode root) {
    if (root == null) return null;
    TreeNode temp = root.left;
    root.left = invert(root.right);
    root.right = invert(temp);
    return root;
}

Build Tree from Preorder & Inorder

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return build(preorder, 0, preorder.length - 1,
                 inorder, 0, inorder.length - 1, map);
}
TreeNode build(int[] pre, int preStart, int preEnd,
               int[] in, int inStart, int inEnd,
               Map<Integer, Integer> map) {
    if (preStart > preEnd || inStart > inEnd) return null;
    TreeNode root = new TreeNode(pre[preStart]);
    int rootIdx = map.get(root.val);
    int leftSize = rootIdx - inStart;
    root.left = build(pre, preStart + 1, preStart + leftSize,
                      in, inStart, rootIdx - 1, map);
    root.right = build(pre, preStart + leftSize + 1, preEnd,
                       in, rootIdx + 1, inEnd, map);
    return root;
}

AVL Tree

Rotations

TreeNode rightRotate(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;
    x.right = y;
    y.left = T2;
    return x;
}

TreeNode leftRotate(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;
    y.left = x;
    x.right = T2;
    return y;
}

Insert with Balancing

TreeNode insertAVL(TreeNode root, int val) {
    // Normal BST insert
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insertAVL(root.left, val);
    else if (val > root.val) root.right = insertAVL(root.right, val);
    else return root;

    // Update height and balance
    int balance = getBalance(root);
    // Left‑Left
    if (balance > 1 && val < root.left.val)
        return rightRotate(root);
    // Right‑Right
    if (balance < -1 && val > root.right.val)
        return leftRotate(root);
    // Left‑Right
    if (balance > 1 && val > root.left.val) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }
    // Right‑Left
    if (balance < -1 && val < root.right.val) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }
    return root;
}

int getBalance(TreeNode root) {
    if (root == null) return 0;
    return height(root.left) - height(root.right);
}

Common Tree Problems

Easy

Maximum Depth of Binary Tree
Invert Binary Tree
Symmetric Tree
Same Tree
Path Sum

Medium

Binary Tree Level Order
Validate BST
Diameter of Binary Tree
Lowest Common Ancestor
Kth Smallest in BST

Hard

Serialize / Deserialize Binary Tree
Binary Tree Maximum Path Sum
Word Ladder
Recover BST

Complexities Summary

Operation	BST (avg)	BST (worst)	AVL / RB
Search	O(log n)	O(n)	O(log n)
Insert	O(log n)	O(n)	O(log n)
Delete	O(log n)	O(n)	O(log n)
Traversal (DFS/BFS)	O(n)

📌 Quick Reference

DFS: Pre‑order (root first), In‑order (sorted for BST), Post‑order (children first)
BFS: Level order – use Queue
BST: Left < parent < right
AVL: BST with balance factor ≤ 1
LCA: Lowest common ancestor of two nodes

← Back to All Cheatsheets