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; }

  1. 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; }

  1. Search value
  2. 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; }

  1. 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; }

  1. 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; }

  1. 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; }

  1. 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; }

  1. Level/vertical/zigzag order traversal:

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

  1. 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; }

  1. 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; }

  1. 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; }

results matching ""

    No results matching ""