Binary Search Tree

   2

  / \

 1   4

    / \

   3   5

In-order traversal: 1 - 2 - 3 - 4 - 5

Pre-order traversal: 2 - 1 - 4 - 3 - 5

Post-order traversal: 1 - 3 - 5 - 4 - 2

Recursive Traversal

In-order:

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

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> rlist = new ArrayList<Integer>();
        inTra(root, rlist);
        return rlist;
    }

    private void inTra(TreeNode root, List<Integer> rlist)
    {
        if(root == null)
        {
            return;
        }
        inTra(root.left, rlist);
        rlist.add(root.val);
        inTra(root.right, rlist);
    }
}

Pre-order:

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rlist = new ArrayList<Integer>();
        preTra(root, rlist);
        return rlist;
    }

    private void preTra(TreeNode root, List<Integer> rlist)
    {
        if(root == null)
        {
            return;
        }
        rlist.add(root.val);
        preTra(root.left, rlist);
        preTra(root.right, rlist);
    }
}

Post-order:

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rlist = new ArrayList<Integer>();
        preTra(root, rlist);
        return rlist;
    }

    private void preTra(TreeNode root, List<Integer> rlist)
    {
        if(root == null)
        {
            return;
        }
        preTra(root.left, rlist);
        preTra(root.right, rlist);
        rlist.add(root.val);
    }
}

Iterative Traversal

In-order

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode curt = root;
        while (curt != null || !stack.empty()) {
            while (curt != null) {
                stack.add(curt);
                curt = curt.left;
            }
            curt = stack.pop();            
            result.add(curt.val);
            curt = curt.right;
        }
        return result;
    }
}

Pre-order

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rlist = new ArrayList<Integer>();
        TreeNode cur = root;
        Stack<TreeNode> stk = new Stack<TreeNode>();
        while(cur != null || !stk.isEmpty())
        {
            while(cur != null)
            {
                rlist.add(cur.val);
                stk.push(cur);
                cur = cur.left;
            }
            cur = stk.pop();
            cur = cur.right;
        }
        return rlist;
    }
}

Post-order

public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode prev = null; // previously traversed node
    TreeNode curr = root;

    if (root == null) {
        return result;
    }

    stack.push(root);
    while (!stack.empty()) {
        curr = stack.peek();
        if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            }
        } else if (curr.left == prev) { // traverse up the tree from the left
            if (curr.right != null) {
                stack.push(curr.right);
            }
        } else { // traverse up the tree from the right
            result.add(curr.val);
            stack.pop();
        }
        prev = curr;
    }

    return result;
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null) {
            stack.push(root); 
            root = root.left == null? root.right: root.left;   
        }
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            if (!stack.isEmpty()) {
                TreeNode parent = stack.peek();
                if (cur == parent.left) {
                    cur = parent.right;
                    while (cur != null) {
                        stack.push(cur);
                        cur = cur.left == null? cur.right: cur.left;
                    }
                }
            }
        }
        return result;
    }
}

Insert value into a BST:

recursive:

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

Iterative:

public void insert(Node root, int value) {
    Node cur = root;
    Node parent = null;
    while (cur != null) {
        parent = cur;
        if (cur.val > value) {
        cur = cur.left;
        } else {
        cur = cur.right;
        }
    }
    if (parent.val > value) {
        parent.left = new Node(value);
    } else {
        parent.right = new Node(value);
    }
}

Remove node from a BST: (after removing we either take largest value from left subtree, or min value from right subtree to replace the removed node)

Recursive:

public Node remove(Node root, int value) {
    if (root == null) {
        return root;
    }
    if (root.val < value) {
        root.right = remove(root.right, value);
    } else if (root.val > value) {
        root.left = remove(root.left, value);
    } else {
        if (root.left == null || root.right == null) {
            return root.left == null ? root.right : root.left;
        }
        root.val = findSmallest(root.right);
        root.right = remove(root.right, root.val);
    }
    return root;
}

private int findSmallest(Node root) {
    int min;
    while (root != null) {
        min = root.key;
        root = root.left;
    }
    return min;
}

Iterative: