Trees

Types of Binary Trees

https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

A full binary tree is a tree in which every node has either 0 or 2 children.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

A perfect binary tree is a tree with all leaves are at the same level, and every parent has two children.

Binary Tree Node

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

Binary Tree Traversal

Iterative, Non-recursive Implementation with Stack

Pre-Order Traversal

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;   
        }
    }
    return result;
}

*Another Iterative Pre-Order Traversal

public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ans;
    }

In-Order Traversal

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;   
        }
    }
    return result;
}

*Another Iterative In-Order Traversal

public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            ans.add(p.val);
            p = p.right;
        }
        return ans;
    }

Post-Order Traversal

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

*Another Iterative Post-Order Traversal

public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.addFirst(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        return output;
    }

Recursive Implementation

Pre-Order Traversal

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        recursivePreorderTraversal(root, result);
        return result;
    }
    void recursivePreorderTraversal(TreeNode root, List<Integer> result) {
        if (root != null) {
            result.add(root.val);
            recursivePreorderTraversal(root.left, result);
            recursivePreorderTraversal(root.right, result);
        }
    }
}

In-Order Traversal

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        recursiveInorderTravesal(root, result);
        return result;
    }
    void recursiveInorderTravesal(TreeNode root, List<Integer> result) {
        if (root != null) {
            if (root.left != null) {
                recursiveInorderTravesal(root.left, result);
            }
            result.add(root.val);
            if (root.right != null) {
                recursiveInorderTravesal(root.right, result);
            }
        }
    }
}

Post-Order Traversal

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        recursivePreorderTraversal(root, result);
        return result;
    }
    void recursivePreorderTraversal(TreeNode root, List<Integer> result) {
        if (root != null) {
            recursivePreorderTraversal(root.left, result);
            recursivePreorderTraversal(root.right, result);
            result.add(root.val);
        }
    }
}

Level Order Traversal

BFS

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

        if(root == null) return wrapList;

        queue.offer(root);
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();
            for(int i=0; i<levelNum; i++) {
                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            wrapList.add(subList);
        }
        return wrapList;
    }
}

DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        levelOrderHelper(root, 0, result);
        return result;
    }
    void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        if (depth == result.size()) {
            result.add(new ArrayList<Integer>());
        }
        result.get(depth).add(root.val);
        levelOrderHelper(root.left, depth + 1, result);
        levelOrderHelper(root.right, depth + 1, result);

    }
}

Maximum Depth of Binary Tree

Recursive

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

Symmetric Tree

https://leetcode.com/articles/symmetric-tree/

Recursive

public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}
boolean isMirror(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) return true;
    if (node1 == null || node2 == null) return false;
    if (node1.val != node2.val) return false;
    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}

Iterative

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Queue < TreeNode > q = new LinkedList < TreeNode > ();
    q.offer(root.left);
    q.offer(root.right);
    while (!q.isEmpty()) {
        TreeNode n1 = q.poll();
        TreeNode n2 = q.poll();
        if (n1 == null && n2 == null) continue;
        if (n1 == null && n2 != null) return false;
        if (n1 != null && n2 == null) return false;
        if (n1.val != n2.val) return false;
        q.offer(n1.left);
        q.offer(n2.right);
        q.offer(n1.right);
        q.offer(n2.left);
    }
    return true;
}

Binary Search Tree (BST)

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