Preorder(root):
    if root == null: return
    visit root
    Preorder(root.left)
    Preorder(root.right)

Inorder(root):
    left
    root
    right

Postorder(root):
    left
    right
    root

Use Cases

• Expression trees
• BST sorted traversal (inorder)
• Subtree-based DP

Time: O(n)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public void preorder(TreeNode root) {
    if (root == null) return;

    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

public void inorder(TreeNode root) {
    if (root == null) return;

    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

public void postorder(TreeNode root) {
    if (root == null) return;

    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

Initialize queue
Add root

While queue not empty:
    size = queue.size
    For size times:
        node = dequeue
        visit node
        add children

Use Cases

• Level traversal
• Shortest path in tree
• Zigzag traversal

Time: O(n)

public List<List<Integer>> levelOrder(TreeNode root) {
    List<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();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Search(root, key):
    if root == null: return null
    if key == root.val: return root
    if key < root.val:
        search left
    else:
        search right

Property Left subtree < root < right subtree

public TreeNode searchBST(TreeNode root, int key) {
    if (root == null || root.val == key)
        return root;

    if (key < root.val)
        return searchBST(root.left, key);

    return searchBST(root.right, key);
}

public TreeNode insertBST(TreeNode root, int key) {
    if (root == null)
        return new TreeNode(key);

    if (key < root.val)
        root.left = insertBST(root.left, key);
    else
        root.right = insertBST(root.right, key);

    return root;
}

global maxDiameter = 0

Height(node):
    if null: return 0

    left = Height(node.left)
    right = Height(node.right)

    maxDiameter = max(maxDiameter,
                      left + right)

    return 1 + max(left, right)

Time: O(n)

int diameter = 0;

public int height(TreeNode root) {
    if (root == null) return 0;

    int left = height(root.left);
    int right = height(root.right);

    diameter = Math.max(diameter,
                        left + right);

    return 1 + Math.max(left, right);
}

If root is null:
    return null

If root == p OR root == q:
    return root

left = LCA(root.left)
right = LCA(root.right)

If both not null:
    return root

Return non-null child

Time: O(n)

public 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 (left != null && right != null)
        return root;

    return left != null ? left : right;
}

global maxSum = -inf

DFS(node):
    if null: return 0

    left = max(0, DFS(left))
    right = max(0, DFS(right))

    maxSum = max(maxSum,
                 node.val + left + right)

    return node.val + max(left, right)

int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}

private int dfs(TreeNode node) {
    if (node == null) return 0;

    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));

    maxSum = Math.max(maxSum,
            node.val + left + right);

    return node.val +
           Math.max(left, right);
}

Build(node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid
        build left child
        build right child
        tree[node] = left + right

Query(node, start, end, L, R):
    if outside: return 0
    if fully inside: return tree[node]
    return leftQuery + rightQuery

Time

• Build: O(n)
• Query/Update: O(log n)

class SegmentTree {

    int[] tree;
    int n;

    SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        build(nums, 0, 0, n - 1);
    }

    void build(int[] nums,
               int node,
               int start,
               int end) {

        if (start == end) {
            tree[node] = nums[start];
        } else {
            int mid = (start + end) / 2;
            build(nums, 2*node+1,
                  start, mid);
            build(nums, 2*node+2,
                  mid+1, end);
            tree[node] =
                tree[2*node+1] +
                tree[2*node+2];
        }
    }
}

Insert word char by char
Traverse children
Mark end

Used For

• Dictionary search
• Autocomplete
• Word search problems

Time: O(length)

class TrieNode {
    TrieNode[] children =
        new TrieNode[26];
    boolean isEnd;
}

class Trie {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;

        for (char c :
             word.toCharArray()) {

            int idx = c - 'a';
            if (node.children[idx] == null)
                node.children[idx] =
                    new TrieNode();

            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;

        for (char c :
             prefix.toCharArray()) {

            int idx = c - 'a';
            if (node.children[idx] == null)
                return false;

            node = node.children[idx];
        }
        return true;
    }
}