# Binary Search Tree

Part I: Basic operations

1. Insert Node

``````public static TreeNode insert(TreeNode head, int val) {
}
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;
}
}

}
``````
2. Delete value

``````public static TreeNode delete(TreeNode head, int val) {
return null;
}
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
} else {
if (prev.left == n) {
prev.left = n.right;
} else {
prev.right = n.right;
}
}

}
``````
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();
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();
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();
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;
}

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) {
return null;
}

}

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.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 "";
}
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]));
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.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;
}

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++));
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;
}
``````