Skip to content

Instantly share code, notes, and snippets.

@amadrzyk

amadrzyk/BinaryTreeTraversal.java

Created October 4, 2016 03:24
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save amadrzyk/da2bfa8bd7a01ef8066f299ca203c8e2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save amadrzyk/da2bfa8bd7a01ef8066f299ca203c8e2 to your computer and use it in GitHub Desktop.
Download ZIP
Week 3 – Western Tech Interview Prep
Raw
BinaryTreeTraversal.java
import java.util.*;
public class BinaryTreeTraversal {
// Definition for a binary tree node.
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static List<Integer> inorderTraversal(TreeNode root) {
// BASE CASE
if (root == null) return new ArrayList<Integer>();
// RECURSIVE CASE
else {
// left
List<Integer> list = new ArrayList<Integer>();
if (root.left != null){
list.addAll(inorderTraversal(root.left));
}
// node
list.add(root.val);
// right
if (root.right != null){
list.addAll(inorderTraversal(root.right));
}
return list;
}
}
public static List<Integer> preorderTraversal(TreeNode root){
// BASE CASE
if (root == null) return new ArrayList<Integer>();
// RECURSIVE CASE
else {
List<Integer> list = new ArrayList<Integer>();
// node
list.add(root.val);
// left
if (root.left != null){
list.addAll(preorderTraversal(root.left));
}
// right
if (root.right != null){
list.addAll(preorderTraversal(root.right));
}
return list;
}
}
public static List<Integer> postorderTraversal(TreeNode root){
// BASE CASE
if (root == null) return new ArrayList<Integer>();
// RECURSIVE CASE
else {
List<Integer> list = new ArrayList<Integer>();
if (root.left != null){
list.addAll(postorderTraversal(root.left));
}
if (root.right != null){
list.addAll(postorderTraversal(root.right));
}
list.add(root.val);
return list;
}
}
public static void main(String[] args){
TreeNode root = new TreeNode(1);
TreeNode two = new TreeNode(2);
TreeNode three = new TreeNode(3);
root.left = null;
root.right = two;
two.left = three;
two.right = null;
three.left = null;
three.right = null;
List<Integer> listInOrder = inorderTraversal(root);
List<Integer> listPreOrder = preorderTraversal(root);
List<Integer> listPostOrder = postorderTraversal(root);
System.out.print("InOrder:\t");
for (int i : listInOrder){
System.out.printf("%d ", i);
}
System.out.printf("\nPreOrder:\t");
for (int i : listPreOrder){
System.out.printf("%d ", i);
}
System.out.printf("\nPostOrder:\t");
for (int i : listPostOrder){
System.out.printf("%d ", i);
}
}
}
Raw
CloneGraph.java
import java.util.*;
public class CloneGraph {
public static class UndirectedGraphNode {
int label;
List<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
};
// Create a map that will be used to store already-created clones
HashMap<Integer, UndirectedGraphNode> map = new HashMap<Integer, UndirectedGraphNode>();
// ORIGINAL FUNCITON, INITIATES RECURSION
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return clone(node);
}
// RECURSIVE FUNCTION
public UndirectedGraphNode clone(UndirectedGraphNode node) {
// Base Cases
if (node == null){
return null;
}
if (map.containsKey(node.label)) {
return map.get(node.label);
}
// Each pass will have a new clone, will also add it to the map (iff it's not already in there)
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(clone.label, clone);
// Recursion visits each node until you reach one already in the map
for (UndirectedGraphNode neighbor : node.neighbors) {
clone.neighbors.add(clone(neighbor));
}
return clone;
}
}
Raw
IsValidBST.java
import java.util.*;
public class IsValidBST {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE, list);
}
public static boolean isValidBSTHelper(TreeNode root, int min, int max, List<Integer> list){
if (root == null) return true;
// Checks if the current node is outside of the current bounds, or if there is a duplicate
if (root.val < min || root.val > max || list.contains(root.val)){
return false;
}
// Makes sure (especially on first pass) that left node isn't greater than current node
if (root.left != null){
if (root.left.val > root.val){
return false;
}
}
// Makes sure (especially on first pass) that right node isn't smaller than current node
if (root.right != null){
if (root.right.val < root.val){
return false;
}
}
// Adds current (visited) node to list to ensure no duplicates
list.add(root.val);
return isValidBSTHelper(root.left, min, root.val - 1, list) && isValidBSTHelper(root.right, root.val+1, max, list);
}
public static void main(String[] args){
TreeNode one = new TreeNode(1);
TreeNode two = new TreeNode(2);
TreeNode three = new TreeNode(3);
// VALID
TreeNode root = two;
two.left = one;
two.right = three;
one.left = null;
one.right = null;
three.left = null;
three.right = null;
System.out.printf("Is Valid BST Valid? \t%b\n", isValidBST(root));
// INVALID
root = one;
one.left = two;
one.right = three;
two.left = null;
two.right = null;
System.out.printf("Is Invalid BST Valid? \t%b\n", isValidBST(root));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment