Binary Search Tree

Part I: Basic operations

1. Insert Node

   public static TreeNode insert(TreeNode head, int val) {
        if (head == null) {
            head = new TreeNode(val);
            return head;
        }
        TreeNode n = head;
        while (n != null) {
            if (val < n.val) {
                if (n.left == null) {
                    n.left = new TreeNode(val);
                    break;
                }
                n = n.left;
            } else {
                if (n.right == null) {
                    n.right = new TreeNode(val);
                    break;
                }
                n = n.right;
            }
        }
   
        return head;
   }
   

2. Delete value

   public static TreeNode delete(TreeNode head, int val) {
        if (head == null) {
            return null;
        }
        TreeNode n = head;
        TreeNode prev = null;
   
        while (val != n.val) { // find the node to be deleted, prev tracks the parent node, null when head is to be deleted
            prev = n;
            if (val < n.val) {
                //prev = n;
                n = n.left;
            } else {
                //prev = n;
                n = n.right;
            }
        }
        // move the left subtree to be left of the left most node of right subtree
        TreeNode t = n.right;
        while (t != null && t.left != null) {
            t = t.left;
        }
   
        t.left = n.left;
   
        if (prev == null) { // to delete head
            head = n.right;
        } else {
            if (prev.left == n) {
                prev.left = n.right;
            } else {
                prev.right = n.right;
            }
        }
   
        return head;        
   }
   

3. Search value

4. In-order successor/preceder

   public static TreeNode successor(TreeNode root, TreeNode node) {
        if (root == null) {
            return null;
        }
   
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } 
   
        TreeNode n = null;
        TreeNode successor = null;    
        n = root;
        while (n != node) {
            if (n.val > node.val) {
                successor = n;
                n = n.left;
            } else {
                n = n.right;
            }
        }
   
        return successor;
    }
   

5. In-order precessor

   public static TreeNode precessor(TreeNode root, TreeNode node) {
        if (root == null) {
            return null;
        }
   
        if (node.left != null) {
            node = node.left;
            while (node.right != null) {
                node = node.right;
            }
            return node;
        }
   
        TreeNode n = root;
        TreeNode precessor = null;
   
        while (n != node) {
            if (n.val > node.val) {
                n = n.left;
            } else {
                precessor = n;
                n = n.right;
            }
        }
   
        return precessor;
    }
   

6. Verify Preorder Sequence in Binary Search Tree

   public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE, i = -1;
    for (int p : preorder) {
        if (p < low)
            return false;
        while (i >= 0 && p > preorder[i])
            low = preorder[i--];
        preorder[++i] = p;
    }
    return true;
   }
   

   Postorder version

public boolean verifyPostorder(int[] postorder) {
    int high = Integer.Max_VALUE, i = postorder;
    for (int p : postorder) {
        if (p > high)
            return false;
        while (i < postorder.length && p < preorder[i])
            high = preorder[i++];
        preorder[--i] = p;
    }
    return true;
}

Part II: Traversal

1. Pre-order

   public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); 
        if (root == null) {
            return res;
        }
   
        Stack<TreeNode> q = new Stack<>();
        q.push(root);
   
        while (!q.isEmpty()) {
            TreeNode n = q.pop();
            res.add(n.val);
            if (n.right != null) {
                q.push(n.right);
            }
            if (n.left != null) {
                q.push(n.left);
            }
        }
        return res;
   }
   

2. In-order

   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
   
        Stack<TreeNode> stack = new Stack<>();
   
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            }
   
            else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
   

3. Post-order

   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
   
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
   
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right != null && prev != peek.right) {
                    root = peek.right;
                } else {
                    stack.pop();
                    res.add(peek.val);
                    prev = peek;
                }
            }
        }
   
        return res;
    }
   

4. Level/vertical/zigzag order traversal:

   public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
   
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
   
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                tmp.add(n.val);  // change this for different orders
                if (n.left != null) {
                    q.offer(n.left);
                }
                if (n.right != null) {
                    q.offer(n.right);
                }
            }
            res.add(tmp); // change this for different orders
        }
   
        return res;
    }
   

Part III: array/list <-> binary tree

1. sorted array to BST

   public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
   
        return sortedArrayToBST(nums, 0, nums.length-1);
    }
        public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
            if (left > right) {
                return null;
            }
   
            int mid = left + (right-left)/2;
            TreeNode node = new TreeNode(nums[mid]);
            node.left = sortedArrayToBST(nums, left, mid - 1);
            node.right = sortedArrayToBST(nums, mid + 1, right);
            return node;
        }
   

2. sorted list to BST

Iterative version: merge sort like

public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return new TreeNode(head.val);
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.next.val);

        ListNode second = slow.next.next;
        slow.next = null;

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(second);

        return root;
    }

1. Serialize/deserialize Binary tree

easiest way to do: BFS, parent-children with a separating symbol

public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        StringBuilder sb = new StringBuilder();

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                if (n == null) {
                    sb.append("#,");
                } else {
                    sb.append(n.val + ",");
                    q.offer(n.left);
                    q.offer(n.right);
                }

            }
        }

        return sb.toString().substring(0, sb.length()-1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] str = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int index = 1;
        while (index < str.length) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                if (!str[index].equals("#")) {
                    n.left = new TreeNode(Integer.parseInt(str[index]));
                    q.offer(n.left);
                } 
                index++;

                if (!str[index].equals("#")) {
                    n.right = new TreeNode(Integer.parseInt(str[index]));
                    q.offer(n.right);
                }
                index++;
            }
        }

        return root;
    }

1. Serialize/deserialize N-ary tree

   // parent-all children BFS
    public static String serializeTreeIte2(TreeNode root) {
        if (root == null) {
            return new String();
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
   
        while (!queue.isEmpty()) {
            int size = queue.size();
   
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                sb.append(n.c);
                for (TreeNode t : n.children) {
                    queue.offer(t);
                }
            }
            sb.append(')');
        }
   
        return sb.toString();
    }
   
    public static TreeNode deserializeTreeIte2(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
   
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(str.charAt(0));
        queue.offer(root);
        int index = 2;
        while (index < str.length()) {
            int size = queue.size();
   
            for (int i = 0; i < size; i++) {
                TreeNode n = queue.poll();
                while (str.charAt(index) != ')') {
                    TreeNode t = new TreeNode(str.charAt(index++));
                    n.children.add(t);
                    queue.offer(t);
                }
            }
            index++;
        }
   
        return root;
    }
   

2. construct binary tree from postoder+inorder traversal

   public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length != postorder.length || inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }
   
    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
   
        TreeNode root = new TreeNode(postorder[postEnd]);
        int index = 0; 
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == postorder[postEnd]) {
                index = i;
                break;
            }
        }
   
        root.left = buildTree(inorder, inStart, index - 1, postorder, postStart, postStart+index-(inStart+1));
        root.right = buildTree(inorder, index + 1, inEnd, postorder, postStart+index-(inStart), postEnd-1);
   
        return root;
    }
   

3. construct binary tree from preoder+inorder traversal

   public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }    
   
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
   
    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
   
        TreeNode node = new TreeNode(preorder[preStart]);
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == preorder[preStart]) {
                index = i;
                break;
            }
        }
        int k = index-inStart;
        node.left = buildTree(preorder, preStart+1, preStart+k, inorder, inStart, index-1);
        node.right = buildTree(preorder, preStart+k+1, preEnd, inorder, index+1, inEnd);
        return node;
    }