Skip to content

Instantly share code, notes, and snippets.

@steghio

steghio/AAA_BST.txt

Last active July 21, 2021 13:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save steghio/ed5fc0607733b0566faa61d2b9a47ff9 to your computer and use it in GitHub Desktop.
Save steghio/ed5fc0607733b0566faa61d2b9a47ff9 to your computer and use it in GitHub Desktop.
Download ZIP
BST - binary search tree and binary trees
Raw
AAA_BST.txt
BST - binary search tree and binary trees
Raw
AreBSTEqualJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BST;
import com.blogspot.groglogs.bst.BSTUtils;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class AreBSTEqualJTests {
BST t1, t2;
@Test
public void nullEmpty() {
t1 = null;
t2 = null;
assertTrue("null trees are equal", BSTUtils.areEqualBST(t1, t2));
t1 = new BST(1);
t2 = null;
assertFalse("null tree is not equal to not null tree", BSTUtils.areEqualBST(t1, t2));
}
@Test
public void oneNode() {
t1 = new BST(1);
t2 = new BST(2);
assertFalse("one node different value", BSTUtils.areEqualBST(t1, t2));
t1 = new BST(1);
t2 = new BST(1);
assertTrue("one node same value", BSTUtils.areEqualBST(t1, t2));
}
@Test
public void differentNumberOfNodes() {
t1 = new BST(1);
t1.addLeft(2);
t2 = new BST(1);
assertFalse("different number of nodes", BSTUtils.areEqualBST(t1, t2));
}
@Test
public void sameNodesDifferentChildren() {
t1 = new BST(1);
t1.addLeft(2);
t2 = new BST(1);
t2.addLeft(3);
assertFalse("same number of nodes, different children", BSTUtils.areEqualBST(t1, t2));
}
/*
X means null
1
2 3
4 X 5 X
XX XX 6 7 XX
*/
@Test
public void sampleBST() {
t1 = new BST(1);
t1.left = new BST(2);
t1.right = new BST(3);
t1.left.left = new BST(4);
t1.right.left = new BST(5);
t1.right.left.left = new BST(6);
t1.right.left.right = new BST(7);
t2 = new BST(1);
t2.left = new BST(2);
t2.right = new BST(3);
t2.left.left = new BST(4);
t2.right.left = new BST(5);
t2.right.left.left = new BST(6);
t2.right.left.right = new BST(7);
assertTrue("sample tree", BSTUtils.areEqualBST(t1, t2));
}
}
Raw
BST.java
package com.blogspot.groglogs.bst;
import com.blogspot.groglogs.bst.structures.BST;
import com.blogspot.groglogs.bst.structures.Entry;
import com.blogspot.groglogs.bst.structures.Pair;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
public class BSTUtils {
//used in serializeBST and deserializeBST
private final static String VAL_SEP = ",", NULL_VAL = "X";
/*
preorder visit: root, left, right
inorder visit: left, root, right
postorder visit: left, right, root
*/
private static List<Integer> doPreorderVisit(BST root, List<Integer> out){
if(root != null){
out.add(root.getVal());
doPreorderVisit(root.left, out);
doPreorderVisit(root.right, out);
}
return out;
}
public static List<Integer> preorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);
return out;
}
public static int[] preorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
private static List<Integer> doInorderVisit(BST root, List<Integer> out){
if(root != null){
doInorderVisit(root.left, out);
out.add(root.getVal());
doInorderVisit(root.right, out);
}
return out;
}
public static List<Integer> inorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);
return out;
}
public static int[] inorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
//iterative inorder visit, use a stack as helper structure
private static List<Integer> doInorderVisitIterative(BST root, List<Integer> out){
if(root == null) return out;
BST curr = root;
Stack<BST> s = new Stack<>();
//keep looping as long as we have at least one valid element
while(!s.isEmpty() || curr != null){
//if current element is not null, keep stacking the left children
if(curr != null){
s.push(curr);
curr = curr.left;
}
//when we get a null, move up the tree (in stack view) again, visit the node, and switch to the right subtree
else{
curr = s.pop();
out.add(curr.getVal());
curr = curr.right;
}
}
return out;
}
public static List<Integer> inorderVisitListIterative(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisitIterative(root, out);
return out;
}
public static int[] inorderVisitIterative(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisitIterative(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
private static List<Integer> doPostorderVisit(BST root, List<Integer> out){
if(root != null){
doPostorderVisit(root.left, out);
doPostorderVisit(root.right, out);
out.add(root.getVal());
}
return out;
}
public static List<Integer> postorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);
return out;
}
public static int[] postorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
public static List<Integer> BFSVisitList(BST root){
if(root == null) return null;
List<Integer> out = new ArrayList<>();
Queue<BST> q = new LinkedList<BST>();
q.add(root);
while(!q.isEmpty()){
BST t = q.remove();
out.add(t.getVal());
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
return out;
}
public static int[] BFSVisit(BST root){
if(root == null) return null;
int[] res = null;
List<Integer> out = BFSVisitList(root);
if(out != null) res = out.stream().mapToInt(i -> i).toArray();
return res;
}
/*
We can build a Binary Tree from its preorder and inorder visits as such:
- in the preorder at position 0 we have the root
- in the inorder before the index of the root found at previous step, we have the left subtree and after we have the right subtree
- we can determine a range to search for our elements inside and recursively compute the left and right subtrees for each subroot
CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays
However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object
*/
private static BST doBuild(int[] preorder, int[] inorder, int start, int end, int root_idx, Map<Integer, Integer> in_map){
if(end <= start) return null; //this is the child of a leaf
BST t = new BST(preorder[root_idx]); //add ourselves as root
//find this root in the inorder visit
int subroot_idx = in_map.get(preorder[root_idx]);
/*
the left subtree should search for the root immediately adjacent the current one in the preorder visit (root_idx + 1)
it should search for the rest of the subtree in the portion between our start and the current subroot (start to subroot_idx) in the inorder visit
*/
t.setLeft(doBuild(preorder, inorder, start, subroot_idx, root_idx + 1, in_map));
/*
the right subtree should search for the root immediately adjacent the last left subtree element we checked in the preorder visit (root_idx + 1 + subroot_idx - start)
it should search for the rest of the subtree in the portion between our current subroot and the our end (subroot_idx + 1 to end) in the inorder visit
*/
t.setRight(doBuild(preorder, inorder, subroot_idx + 1, end, root_idx + 1 + subroot_idx - start, in_map));
return t;
}
public static BST buildTreeFromVisit(int[] preorder, int[] inorder){
if(preorder == null || inorder == null || preorder.length != inorder.length) return null;
/*
with this we bring time down from O(N^2) to O(N) and are still in O(N) space
Map from value to index in array
*/
HashMap<Integer, Integer> in_map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
in_map.put(inorder[i], i);
}
BST out = doBuild(preorder, inorder, 0, preorder.length, 0, in_map);
return out;
}
//find depth of the tree
public static int getTreeDepth(BST root){
if(root == null) return -1;
return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;
}
/*
is tree balanced
A tree is balanced if the left and right branches do not differ for more than 1 level in length
*/
private static Entry isTreeBalancedAux(BST root){
//null root is always balanced
if(root == null) return new Entry(true, -1);
Entry left, right;
//check subtrees
left = isTreeBalancedAux(root.left);
right = isTreeBalancedAux(root.right);
//if they are not balanced, we have our answer
if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);
//otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced
if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);
//finally, if all is good, return the max depth from this node including itself and mark it as balanced
return new Entry(true, Math.max(left.height, right.height) + 1);
}
public static boolean isTreeBalanced(BST root){
return isTreeBalancedAux(root).isBalanced;
}
/*
is tree complete
A tree is complete if for each level, there are no holes between children:
complete =
A
B C
no holes between B and C
complete =
A
B
no holes after B
non complete =
A
C
hole before C
*/
public static boolean isTreeComplete(BST root){
//null root is always complete
if(root == null) return true;
/*
otherwise, we must NOT have null nodes between two nodes at each level
so do a BFS BUT CAUTION: track also NULL children, then check we do not have a non null node after we encountered a null one
*/
Queue<BST> levels = new LinkedList<>();
boolean has_null = false;
levels.add(root);
while(!levels.isEmpty()){
BST t = levels.remove();
//if current node is not null
if(t != null) {
//if we had a null, fail
if(has_null) return false;
//otherwise add its children
levels.add(t.left);
levels.add(t.right);
}
//track if the node we just saw was null. CAUTION: do not overwrite it!
has_null = has_null || t == null;
}
//if we navigated the whole tree without problem, it is complete
return true;
}
//helper for getLeaves
public static List<BST> gatherLeaves(BST node, List<BST> out){
if(node != null){
//if we are a leaf, add us to the result
if(node.left == null && node.right == null) out.add(node);
gatherLeaves(node.left, out);
gatherLeaves(node.right, out);
}
return out;
}
//gather all the tree leaves in a list
public static List<BST> getLeaves(BST node){
if(node == null) return null;
return gatherLeaves(node, new LinkedList<>());
}
//is a list of nodes equal
public static boolean isEqualNodeList(List<BST> nodeList, List<BST> otherNodeList){
if(nodeList == null) return otherNodeList == null;
if(otherNodeList == null) return false;
if(nodeList.size() != otherNodeList.size()) return false;
for(int i = 0; i < nodeList.size(); i++){
if(nodeList.get(i).val != otherNodeList.get(i).val) return false;
}
return true;
}
/**
* Verifies whether this tree is a valid BST using a inorder visit.
* When inserting a node in the tree we move left or right down until we find a spot where to place him.
* Therefore the location of a node is constrained by boundaries set from elements at the previous levels.
* For example a node X can NEVER be in the RIGHT subtree of a node that has a higher value than X.
* The inorder visit gives us the nodes in their natural order, if we find inconsistencies there, the tree is not a valid BST.
* @param t the tree to check.
* @return true if all nodes in this tree respect the BST rule. A null tree is always a valid BST.
*/
public static boolean isValidBSTWithInorderVisit(BST t){
if(t == null){
return true;
}
List<Integer> inorderVisit = doInorderVisit(t, new ArrayList<>());
for(int i = 0; i < inorderVisit.size() - 1; i++){
if(inorderVisit.get(i) > inorderVisit.get(i + 1)){
return false;
}
}
return true;
}
/**
* Given a BST return a string serialization of it. Use comma as value separator and X as marker for nulls.
* @param t the tree to serialize.
* @return the string serialization of the given tree.
*/
public static String serializeBST(BST t){
if(t == null){
return "";
}
StringBuilder sb = new StringBuilder();
int nullsInNextLevel = 0, level = 0, elementsInThisLevel = 0;
Queue<BST> nodes = new LinkedList<>();
nodes.add(t);
/*
Walk on the tree level by level and add values to our string. Also track null children at any level.
We count how many nodes we add to determine at which level of the tree are we. By also handling nulls, we do not
miss any position.
We know we need to stop when the amount of children at the NEXT level that are null equals the maximum amount
of nodes allowed at that level.
*/
while(!nodes.isEmpty()){
//if next level is full of nulls, we are done since we just processed all the leaves
if(nullsInNextLevel == Math.pow(2, level + 1)){
break;
}
//if we processed the maximum amount of elements at this level, we are starting a new level
if(elementsInThisLevel == Math.pow(2, level)){
level++;
elementsInThisLevel = 0;
nullsInNextLevel = 0;
}
BST curr = nodes.poll();
BST left, right;
//if this node is not null, add its value and track its children
if(curr != null){
sb.append(curr.val);
left = curr.left;
right = curr.right;
}
//otherwise add null value and track two fake null children
else {
sb.append(NULL_VAL);
left = null;
right = null;
}
sb.append(VAL_SEP);
elementsInThisLevel++;
//if the children are null, remember that BUT also add them to the queue
if(left == null){
nullsInNextLevel++;
}
nodes.add(left);
if(right == null){
nullsInNextLevel++;
}
nodes.add(right);
}
return sb.toString();
}
/**
* From the given serialization of a BST and a start index, retrieve, if possible, the value of the node in that
* position in the given string.
* @param serializedBST the string representation of the serialized BST.
* @param start the start position in our string where to search the value from.
* @return the value of the node starting at the given position in the string.
* @throws IllegalArgumentException if there is no value (two value separators found adjacent)
* or the given start index is outside of the string boundaries.
*/
private static String getSerializedVal(String serializedBST, int start){
//if we use indexOf and substring we walk the same portion twice
//better approach is to walk and track ourselves all read characters until the marker so we only walk once
StringBuffer sb = new StringBuffer();
for(int i = start; i < serializedBST.length(); i++){
if(serializedBST.charAt(i) == VAL_SEP.charAt(0)){
break;
}
sb.append(serializedBST.charAt(i));
}
if(sb.toString().length() == 0){
throw new IllegalArgumentException("Bad serialization, string");
}
return sb.toString();
}
/**
* Given a serialized value for a BST node, convert it to the corresponding int value.
* @param serializedVal the string representation of a node value. Should be an integer.
* @return the integer corresponding to the serialized node value.
* @throws IllegalArgumentException if the given representation is not a valid integer number.
*/
private static int convertSerializedValToInt(String serializedVal){
try{
return Integer.parseInt(serializedVal);
} catch(NumberFormatException e){
throw new IllegalArgumentException("Invalid value " + serializedVal + " found");
}
}
/**
* Given a string representation of a BST, rebuild the tree corresponding to that serialization.
* @param serializedBST the serialized BST string representation.
* @return the head of the rebuilt BST.
* @throws IllegalArgumentException if the given representation is not a valid BST.
*/
public static BST deserializeBST(String serializedBST){
if(serializedBST == null || serializedBST.length() == 0){
return null;
}
//immediately try to get the root
String serializedVal = getSerializedVal(serializedBST, 0);
BST head = new BST(convertSerializedValToInt(serializedVal));
//we add all nodes to a queue and keep walking the string, each time we expect two children for a node
//if children or node were null, still add them to the queue and simply skip processing them
Queue<BST> nodes = new LinkedList<>();
nodes.add(head);
//track in which position in the serialized string are we after each value read attempt
int stringPosition = serializedVal.length() + 1;
/*
for each node we pop, its two children will be exactly adjacent in the given serialization string starting from
the index where we currently are. If we had null values, we skip them but treat them as nodes with two null
children and add everything to the queue. We stop when the reach the end of the input string.
If there was a problem, it will be raised by the internal logic, otherwise the only nodes left in the queue
will be null markers.
*/
while(!nodes.isEmpty()) {
if(stringPosition >= serializedBST.length()){
break;
}
BST currNode = nodes.poll();
//these portions are identical, could be improved with a function returning a Pair<node, charactersRead>
//attempt to build left child
serializedVal = getSerializedVal(serializedBST, stringPosition);
if(!serializedVal.equals(NULL_VAL)){
currNode.left = new BST(convertSerializedValToInt(serializedVal));
nodes.add(currNode.left);
}
else{
nodes.add(null);
}
stringPosition += serializedVal.length() + 1;
//attempt to build right child
serializedVal = getSerializedVal(serializedBST, stringPosition);
if(!serializedVal.equals(NULL_VAL)){
currNode.right = new BST(convertSerializedValToInt(serializedVal));
nodes.add(currNode.right);
}
else{
nodes.add(null);
}
stringPosition += serializedVal.length() + 1;
}
return head;
}
/**
* Given two BST, checks if they are identical. To be identical, they need to have the exact same values in the exact
* same node positions.
* @param t1 the first tree.
* @param t2 the second tree.
* @return true if the two BSTs are identical.
*/
public static boolean areEqualBST(BST t1, BST t2){
if(t1 == null && t2 == null){
return true;
}
//we just do a parallel BFS on both and break as soon as we find something not matching
if(t1 != null && t2 != null){
Queue<BST> t1Nodes = new LinkedList<>(), t2Nodes = new LinkedList<>();
t1Nodes.add(t1);
t2Nodes.add(t2);
while(!t1Nodes.isEmpty() && !t2Nodes.isEmpty()){
BST t1Node = t1Nodes.poll();
BST t2Node = t2Nodes.poll();
if(t1Node.val != t2Node.val){
return false;
}
//handle nulls in left child
if(t1Node.left != null && t2Node.left !=null){
t1Nodes.add(t1Node.left);
t2Nodes.add(t2Node.left);
}
else{
if(!(t1Node.left == null && t2Node.left ==null)){
return false;
}
}
//handle nulls in right child
if(t1Node.right != null && t2Node.right !=null){
t1Nodes.add(t1Node.right);
t2Nodes.add(t2Node.right);
}
else{
if(!(t1Node.right == null && t2Node.right ==null)){
return false;
}
}
}
//if we broke the loop but one queue is not empty, the trees cannot be identical since one has more elements
if(t1Nodes.isEmpty() && t2Nodes.isEmpty()){
return true;
}
}
return false;
}
/**
* Given a BST, invert it in place. All right children become left and all left children become right.
* @param t the tree to invert.
*/
public static void invertBST(BST t){
if(t == null){
return;
}
/*
Do BFS, we have O(N) extra space for the queue, exactly O(N/2) as worst case is full tree and we add all leaves to the queue
Do DFS or use recursion, we have O(log N) for the stack as worst case is full tree but we process one leaf at a time
so in the stack we only have the path to that leaf, which is at most log N elements
If we use queue and remove from the end, we also have space usage as DFS
*/
BST left = t.left;
t.left = t.right;
t.right = left;
if(t.left != null){
invertBST(t.left);
}
if(t.right != null){
invertBST(t.right);
}
}
//helper for findFloorAndCeil
/*
Walk down the tree setting boundaries each time where the floor and ceil for a specific value would be.
If we find the value, set it as result, otherwise check how to navigate and update floor and ceil accordingly.
When we reach a null (moved out of a leaf) our value is not in the tree so floor and ceil are the last we had.
Our tree is of integers so we use MIN and MAX int as initial values for our bounds.
*/
private static Pair<Integer, Integer> findFloorAndCeil(BST t, int val, int floor, int ceil){
if(t == null){
return new Pair(floor, ceil);
}
if(t.val == val){
return new Pair(val, val);
}
if(t.val > val){
return findFloorAndCeil(t.left, val, floor, t.val);
}
return findFloorAndCeil(t.right, val, t.val, ceil);
}
/**
* Given a BST, find the floor and ceil for a given value, if either does not exist, print them as min or max int.
* If the value is a node, both floor and ceil are that value.
* @param t the tree.
* @param val the value to find floor and ceiling for.
* @return the floor and ceiling for the given value in the tree.
*/
public static Pair<Integer, Integer> findFloorAndCeil(BST t, int val){
if(t == null){
return new Pair<>(Integer.MIN_VALUE, Integer.MAX_VALUE);
}
return findFloorAndCeil(t, val, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
/**
* Given a binary tree, list the values of nodes we would see by looking at it from the right side.
* @param t the tree.
* @return list of values that are the rightmost value of each level in the tree.
*/
public static List<Integer> rightSideView(BST t){
List<Integer> out = new ArrayList<>();
if(t == null){
return out;
}
/*
We do BFS and add a marker to indicate end of a level. We enqueue nodes as a normal BFS.
When we dequeue a node, we check if the next in the queue is the marker, if yes we add this node to the result,
then enqueue its children (if any) and add the marker back ONLY if there were elements left after us.
*/
final BST marker = null;
Queue<BST> q = new LinkedList();
q.add(t);
q.add(marker);
while(!q.isEmpty()){
//process this node and add its children to the queue
BST curr = q.remove();
if(curr.left != null){
q.add(curr.left);
}
if(curr.right != null){
q.add(curr.right);
}
//if the next node is the marker, we are the last on this level, add us to the result
//then remove the marker and add it back to the end of the queue ONLY if there are still elements there
//otherwise we are the very last node in the tree and there is nowhere else to go to continue
if(q.peek() == marker){
out.add(curr.val);
q.remove();
if(!q.isEmpty()){
q.add(marker);
}
}
}
return out;
}
}
Raw
BSTJTests.java
package com.blogspot.groglogs.test.bst;
import org.junit.Test;
import com.blogspot.groglogs.bst.BST;
import com.blogspot.groglogs.bst.BSTUtils;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class BSTJTests {
BST tree = null, node = null;
int[] input = null, preorder = null, inorder = null, postorder = null, output = null, bfs = null;
List<Integer> path = null;
int depth = 0, val;
boolean isBalanced = false, isComplete = false;
List<BST> leaves = null, out = null;
@Test
//null or empty input, we cannot print so we expect NullPointerExceptions
public void nullEmpty() {
//null
input = null;
tree = BST.buildUnbalanced(input);
System.out.println("NULL tree is:");
try{
tree.printTree();
}catch(NullPointerException e){
System.out.println("Got NullPointerException because tree is NULL");
}
//null tree has no leaves
assertEquals("null tree has no leaves", null, BSTUtils.getLeaves(tree));
//null with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("NULL tree with parent is:");
try{
tree.printTreeWParent();
}catch(NullPointerException e){
System.out.println("Got NullPointerException because tree is NULL");
}
//null tree has no leaves
assertEquals("null tree with parent has no leaves", null, BSTUtils.getLeaves(tree));
//null balanced AVL
tree = BST.buildBalancedAVL(input);
System.out.println("NULL tree balanced AVL is:");
try{
tree.printTreeWParent();
}catch(NullPointerException e){
System.out.println("Got NullPointerException because tree is NULL");
}
//null tree has no leaves
assertEquals("null tree balanced AVL has no leaves", null, BSTUtils.getLeaves(tree));
//empty
input = new int[]{};
tree = BST.buildUnbalanced(input);
System.out.println("Empty tree is:");
try{
tree.printTree();
}catch(NullPointerException e){
System.out.println("Got NullPointerException because tree is NULL");
}
//empty with parent
input = new int[]{};
tree = BST.buildUnbalancedWParent(input);
System.out.println("Empty tree with parent is:");
try{
tree.printTreeWParent();
}catch(NullPointerException e){
System.out.println("Got NullPointerException because tree is NULL");
}
//empty balanced AVL
input = new int[]{};
tree = BST.buildBalancedAVL(input);
System.out.println("Empty tree balanced AVL is:");
try{
tree.printTreeWParent();
}catch(NullPointerException e){
System.out.println("Got NullPointerException because tree is NULL");
}
}
//printing tests
@Test
//tree where all values are on the right
public void rightTree() {
input = new int[]{1,2,3};
tree = BST.buildUnbalanced(input);
System.out.println("All right tree is:");
tree.printTree();
//all right tree has one leaf
leaves = BSTUtils.getLeaves(tree);
assertEquals("all right tree has one leaf", 1, leaves.size());
assertEquals("all right tree has one leaf value 3", 3, leaves.get(0).getVal());
assertEquals("all right tree size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 1", 1, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 2", 2, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 3", 3, tree.getKthSmallestElement(3).getVal());
try{
tree.getKthSmallestElement(4);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 4 is bigger than current tree size: " + e.getMessage());
}
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("All right tree with parent is:");
tree.printTreeWParent();
//all right tree has one leaf
leaves = BSTUtils.getLeaves(tree);
assertEquals("all right tree with parent has one leaf", 1, leaves.size());
assertEquals("all right tree with parent has one leaf value 3", 3, leaves.get(0).getVal());
assertEquals("all right tree with parent size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 1", 1, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 2", 2, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 3", 3, tree.getKthSmallestElement(3).getVal());
try{
tree.getKthSmallestElement(4);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 4 is bigger than current tree size: " + e.getMessage());
}
//balanced AVL
tree = BST.buildBalancedAVL(input);
System.out.println("All right tree balanced AVL is:");
tree.printTreeWParent();
//all right tree balanced AVL has two leaves
leaves = BSTUtils.getLeaves(tree);
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(3));
assertEquals("all right tree balanced AVL has two leaves", 2, leaves.size());
assertEquals("all right tree balanced AVL has two leaves value 1,3", true, BSTUtils.isEqualNodeList(out,leaves));
assertEquals("all right tree balanced AVL size", input.length, tree.size());
}
@Test
//tree where all values are on the left
public void leftTree() {
input = new int[]{3,2,1};
tree = BST.buildUnbalanced(input);
System.out.println("All left tree is:");
tree.printTree();
//all left tree has one leaf
leaves = BSTUtils.getLeaves(tree);
assertEquals("all left tree has one leaf", 1, leaves.size());
assertEquals("all left tree has one leaf value 1", 1, leaves.get(0).getVal());
assertEquals("all left tree size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 1", 1, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 2", 2, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 3", 3, tree.getKthSmallestElement(3).getVal());
try{
tree.getKthSmallestElement(4);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 4 is bigger than current tree size: " + e.getMessage());
}
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("All left tree with parent is:");
tree.printTreeWParent();
//all left tree has one leaf
leaves = BSTUtils.getLeaves(tree);
assertEquals("all left tree with parent has one leaf", 1, leaves.size());
assertEquals("all left tree with parent has one leaf value 1", 1, leaves.get(0).getVal());
assertEquals("all left tree with parent size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 1", 1, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 2", 2, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 3", 3, tree.getKthSmallestElement(3).getVal());
try{
tree.getKthSmallestElement(4);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 4 is bigger than current tree size: " + e.getMessage());
}
//balanced AVL
tree = BST.buildBalancedAVL(input);
System.out.println("All left tree balanced AVL is:");
tree.printTreeWParent();
//all left tree balanced AVL has two leaves
leaves = BSTUtils.getLeaves(tree);
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(3));
assertEquals("all left tree balanced AVL has two leaves", 2, leaves.size());
assertEquals("all left tree balanced AVL has two leaves value 1,3", true, BSTUtils.isEqualNodeList(out,leaves));
assertEquals("all left tree balanced AVL size", input.length, tree.size());
}
@Test
//random tree
public void randomTree() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
System.out.println("Random tree is:");
tree.printTree();
//random tree has 3 leaves
leaves = BSTUtils.getLeaves(tree);
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(4));
out.add(new BST(20));
assertEquals("random tree has 3 leaves", 3, leaves.size());
assertEquals("random tree has 3 leaves value 1,4,20", true, BSTUtils.isEqualNodeList(out,leaves));
assertEquals("random tree size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 1", 1, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 2", 2, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 4", 4, tree.getKthSmallestElement(3).getVal());
assertEquals("biggest element is 33", 33, tree.getKthSmallestElement(8).getVal());
try{
tree.getKthSmallestElement(9);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 9 is bigger than current tree size: " + e.getMessage());
}
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("Random tree with parent is:");
tree.printTreeWParent();
//random tree has 3 leaves
leaves = BSTUtils.getLeaves(tree);
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(4));
out.add(new BST(20));
assertEquals("random tree with parent has 3 leaves", 3, leaves.size());
assertEquals("random tree with parent has 3 leaves value 1,4,20", true, BSTUtils.isEqualNodeList(out,leaves));
assertEquals("random tree with parent size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 1", 1, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 2", 2, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 4", 4, tree.getKthSmallestElement(3).getVal());
assertEquals("biggest element is 33", 33, tree.getKthSmallestElement(8).getVal());
try{
tree.getKthSmallestElement(9);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 9 is bigger than current tree size: " + e.getMessage());
}
//balanced AVL
tree = BST.buildBalancedAVL(input);
System.out.println("Random tree balanced AVL is:");
tree.printTreeWParent();
//random tree balanced AVL has 4 leaves
leaves = BSTUtils.getLeaves(tree);
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(6));
out.add(new BST(18));
out.add(new BST(33));
assertEquals("random tree balanced AVL has 4 leaves", 4, leaves.size());
assertEquals("random tree balanced AVL has 4 leaves value 1,6,18,33", true, BSTUtils.isEqualNodeList(out,leaves));
assertEquals("random tree balanced AVL size", input.length, tree.size());
}
@Test
//duplicate tree
public void duplicateTree() {
input = new int[]{13, 13, 13};
tree = BST.buildUnbalanced(input);
System.out.println("Duplicate tree is:");
tree.printTree();
//duplicate tree has one leaf
leaves = BSTUtils.getLeaves(tree);
assertEquals("duplicate tree has one leaf", 1, leaves.size());
assertEquals("duplicate tree has one leaf value 13", 13, leaves.get(0).getVal());
assertEquals("duplicate tree size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 13", 13, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 13", 13, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 13", 13, tree.getKthSmallestElement(3).getVal());
try{
tree.getKthSmallestElement(4);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 4 is bigger than current tree size: " + e.getMessage());
}
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("Duplicate tree with parent is:");
tree.printTreeWParent();
//duplicate tree has one leaf
leaves = BSTUtils.getLeaves(tree);
assertEquals("duplicate with parent tree has one leaf", 1, leaves.size());
assertEquals("duplicate with parent tree has one leaf value 13", 13, leaves.get(0).getVal());
assertEquals("duplicate tree with parent size", input.length, tree.size());
//find k-th smallest element
assertEquals("smallest element is 13", 13, tree.getKthSmallestElement(1).getVal());
assertEquals("second smallest element is 13", 13, tree.getKthSmallestElement(2).getVal());
assertEquals("third smallest element is 13", 13, tree.getKthSmallestElement(3).getVal());
try{
tree.getKthSmallestElement(4);
} catch(NoSuchElementException e){
System.out.println("Got NoSuchElementException because 4 is bigger than current tree size: " + e.getMessage());
}
//balanced AVL
tree = BST.buildBalancedAVL(input);
System.out.println("Duplicate tree balanced AVL is:");
tree.printTreeWParent();
//duplicate tree balanced AVL has one node
leaves = BSTUtils.getLeaves(tree);
assertEquals("duplicate tree balanced AVL has one leaf", 1, leaves.size());
assertEquals("duplicate tree balanced AVL size 1", 1, tree.size());
assertEquals("duplicate tree balanced AVL has one leaf 13", 13, leaves.get(0).getVal());
}
//utilities tests
@Test
//tree contains value
public void contains() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
assertEquals("Tree contains 4: true", true, tree.contains(4));
assertEquals("Tree contains 56: false", false, tree.contains(56));
//with parent, we expect no different behaviour
tree = BST.buildUnbalancedWParent(input);
assertEquals("Tree with parent contains 4: true", true, tree.contains(4));
assertEquals("Tree with parent contains 56: false", false, tree.contains(56));
//AVL balanced, we expect no different behaviour
tree = BST.buildBalancedAVL(input);
assertEquals("Tree balanced AVL contains 4: true", true, tree.contains(4));
assertEquals("Tree balanced AVL contains 56: false", false, tree.contains(56));
}
//utilities tests
@Test
//tree nodes are equal
public void isEqualNode() {
input = new int[]{13};
tree = BST.buildUnbalanced(input);
BST otherTree = BST.buildUnbalanced(new int[]{13});
assertEquals("Node 13 equals node 13: true", true, tree.isEqualNode(otherTree));
otherTree = BST.buildUnbalanced(new int[]{56});
assertEquals("Node 13 equals node 56: false", false, tree.isEqualNode(otherTree));
//null node
assertEquals("Node 13 equals node null: false", false, tree.isEqualNode(null));
//with parent, we expect no different behaviour
tree = BST.buildUnbalancedWParent(input);
otherTree = BST.buildUnbalancedWParent(new int[]{13});
assertEquals("Node 13 with parent equals node 13: true", true, tree.isEqualNode(otherTree));
otherTree = BST.buildUnbalancedWParent(new int[]{56});
assertEquals("Node 13 with parent equals node 56: false", false, tree.isEqualNode(otherTree));
//null node
assertEquals("Node 13 with parent equals node null: false", false, tree.isEqualNode(null));
//AVL balanced, we expect no different behaviour
tree = BST.buildBalancedAVL(input);
otherTree = BST.buildBalancedAVL(new int[]{13});
assertEquals("Node 13 balanced AVL equals node 13: true", true, tree.isEqualNode(otherTree));
otherTree = BST.buildBalancedAVL(new int[]{56});
assertEquals("Node 13 balanced AVL equals node 56: false", false, tree.isEqualNode(otherTree));
//null node
assertEquals("Node 13 balanced AVL equals node null: false", false, tree.isEqualNode(null));
}
@Test
//tree node lists are equal
public void isEqualNodeList() {
out = null;
leaves = null;
assertEquals("null node lists are equal", true, BSTUtils.isEqualNodeList(out,leaves));
out = new LinkedList<>();
leaves = new LinkedList<>();
assertEquals("empty node lists are equal", true, BSTUtils.isEqualNodeList(out,leaves));
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(4));
out.add(new BST(20));
leaves = new LinkedList<>();
leaves.add(new BST(1));
leaves.add(new BST(4));
leaves.add(new BST(20));
assertEquals("node lists are equal", true, BSTUtils.isEqualNodeList(out,leaves));
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(4));
out.add(new BST(20));
leaves = new LinkedList<>();
leaves.add(new BST(1));
leaves.add(new BST(4));
assertEquals("node lists missing last are not equal", false, BSTUtils.isEqualNodeList(out,leaves));
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(4));
out.add(new BST(20));
leaves = new LinkedList<>();
leaves.add(new BST(4));
leaves.add(new BST(20));
assertEquals("node lists missing first are not equal", false, BSTUtils.isEqualNodeList(out,leaves));
out = new LinkedList<>();
out.add(new BST(1));
out.add(new BST(4));
out.add(new BST(20));
leaves = new LinkedList<>();
leaves.add(new BST(1));
leaves.add(new BST(20));
assertEquals("node lists missing mid are not equal", false, BSTUtils.isEqualNodeList(out,leaves));
}
@Test
//find tree node
public void find() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
assertEquals("Find node 4: yes", 4, tree.find(4).getVal());
assertEquals("Find node 56: no", null, tree.find(56));
//with parent, we expect no different behaviour
tree = BST.buildUnbalancedWParent(input);
assertEquals("Find node with parent 4: yes", 4, tree.find(4).getVal());
assertEquals("Find node with parent 56: no", null, tree.find(56));
//balanced AVL, we expect no different behaviour
tree = BST.buildBalancedAVL(input);
assertEquals("Find node balanced AVL 4: yes", 4, tree.find(4).getVal());
assertEquals("Find node balanced AVL 56: no", null, tree.find(56));
}
@Test
//find path to element
public void findPath() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
path = tree.findPath(4);
assertEquals("Path to 4 is long 4", 4, path.size());
path = tree.findPath(13);
assertEquals("Path to 13 is long 1", 1, path.size());
path = tree.findPath(56);
assertEquals("Path to 56 is null", null, path);
//with parent, we expect no different behaviour
tree = BST.buildUnbalancedWParent(input);
path = tree.findPath(4);
assertEquals("Path to 4 with parent is long 4", 4, path.size());
path = tree.findPath(13);
assertEquals("Path to 13 with parent is long 1", 1, path.size());
path = tree.findPath(56);
assertEquals("Path to 56 with parent is null", null, path);
//balanced AVL, we expect different behaviour
tree = BST.buildBalancedAVL(input);
path = tree.findPath(4);
assertEquals("Path to 4 balanced AVL is long 1", 1, path.size());
path = tree.findPath(13);
assertEquals("Path to 13 balanced AVL is long 2", 2, path.size());
path = tree.findPath(56);
assertEquals("Path to 56 balanced AVL is null", null, path);
}
@Test
//distance of two elements using path lists
public void distance() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
//one element does not exist in the tree
assertEquals("Distance 4,56 = -1", -1, tree.distance(4, 56));
//neither element exists in the tree
assertEquals("Distance 32,56 = -1", -1, tree.distance(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance 4,18 = 5", 5, tree.distance(4, 18));
//both elements are in the tree on same side and same branch
assertEquals("Distance 2,1 = 1", 1, tree.distance(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance 2,4 = 2", 2, tree.distance(2, 4));
//same non-root element
assertEquals("Distance 33,33 = 0", 0, tree.distance(33, 33));
//same root element
assertEquals("Distance 13,13 = 0", 0, tree.distance(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildUnbalanced(input);
//same duplicate element
assertEquals("Distance duplicate 13,13 = 0", 0, tree.distance(13, 13));
//with parent, we expect no different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//one element does not exist in the tree
assertEquals("Distance with parent 4,56 = -1", -1, tree.distance(4, 56));
//neither element exists in the tree
assertEquals("Distance with parent 32,56 = -1", -1, tree.distance(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance with parent 4,18 = 5", 5, tree.distance(4, 18));
//both elements are in the tree on same side and same branch
assertEquals("Distance with parent 2,1 = 1", 1, tree.distance(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance with parent 2,4 = 2", 2, tree.distance(2, 4));
//same non-root element
assertEquals("Distance with parent 33,33 = 0", 0, tree.distance(33, 33));
//same root element
assertEquals("Distance with parent 13,13 = 0", 0, tree.distance(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildUnbalancedWParent(input);
//same duplicate element
assertEquals("Distance duplicate with parent 13,13 = 0", 0, tree.distance(13, 13));
//balanced AVL, we expect different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
//one element does not exist in the tree
assertEquals("Distance balanced AVL 4,56 = -1", -1, tree.distance(4, 56));
//neither element exists in the tree
assertEquals("Distance balanced AVL 32,56 = -1", -1, tree.distance(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance balanced AVL 2,13 = 2", 2, tree.distance(2, 13));
//both elements are in the tree on same side and same branch
assertEquals("Distance balanced AVL 2,1 = 1", 1, tree.distance(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance balanced AVL 20,6 = 2", 2, tree.distance(20, 6));
//same non-root element
assertEquals("Distance balanced AVL 33,33 = 0", 0, tree.distance(33, 33));
//same root element
assertEquals("Distance balanced AVL 13,13 = 0", 0, tree.distance(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildBalancedAVL(input);
//same duplicate element
assertEquals("Distance duplicate balanced AVL 13,13 = 0", 0, tree.distance(13, 13));
}
@Test
//lowest common ancestor
public void LCA() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
//one element does not exist in the tree
assertEquals("LCA 4,56 = NULL", null, tree.findLCA(4, 56));
//neither element exists in the tree
assertEquals("LCA 32,56 = NULL", null, tree.findLCA(32, 56));
//both elements are in the tree on different sides -> LCA is root
assertEquals("LCA 4,18 = 13", 13, tree.findLCA(4, 18).getVal());
//both elements are in the tree on same side and same branch -> one is parent of the other and also the LCA
assertEquals("LCA 2,1 = 2", 2, tree.findLCA(2, 1).getVal());
//both elements are in the tree on same side but different branches -> one is parent of the other and also the LCA
assertEquals("LCA 2,4 = 2", 2, tree.findLCA(2, 4).getVal());
//same non-root element -> LCA is the element itself
assertEquals("LCA 33,33 = 33", 33, tree.findLCA(33, 33).getVal());
//same root element -> LCA is the element itself and also the root
assertEquals("LCA 13,13 = 13", 13, tree.findLCA(13, 13).getVal());
input = new int[]{13, 13, 13};
tree = BST.buildUnbalanced(input);
//same duplicate element -> LCA is the element itself and also the root
assertEquals("LCA duplicate 13,13 = 13", 13, tree.findLCA(13, 13).getVal());
//with parent, we expect no different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//one element does not exist in the tree
assertEquals("LCA with parent 4,56 = NULL", null, tree.findLCA(4, 56));
//neither element exists in the tree
assertEquals("LCA with parent 32,56 = NULL", null, tree.findLCA(32, 56));
//both elements are in the tree on different sides -> LCA is root
assertEquals("LCA with parent 4,18 = 13", 13, tree.findLCA(4, 18).getVal());
//both elements are in the tree on same side and same branch -> one is parent of the other and also the LCA
assertEquals("LCA with parent 2,1 = 2", 2, tree.findLCA(2, 1).getVal());
//both elements are in the tree on same side but different branches -> one is parent of the other and also the LCA
assertEquals("LCA with parent 2,4 = 2", 2, tree.findLCA(2, 4).getVal());
//same non-root element -> LCA is the element itself
assertEquals("LCA with parent 33,33 = 33", 33, tree.findLCA(33, 33).getVal());
//same root element -> LCA is the element itself and also the root
assertEquals("LCA with parent 13,13 = 13", 13, tree.findLCA(13, 13).getVal());
input = new int[]{13, 13, 13};
tree = BST.buildUnbalancedWParent(input);
//same duplicate element -> LCA is the element itself and also the root
assertEquals("LCA duplicate with parent 13,13 = 13", 13, tree.findLCA(13, 13).getVal());
//with balanced AVL, we expect different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
//one element does not exist in the tree
assertEquals("LCA balanced AVL 4,56 = NULL", null, tree.findLCA(4, 56));
//neither element exists in the tree
assertEquals("LCA balanced AVL 32,56 = NULL", null, tree.findLCA(32, 56));
//both elements are in the tree on different sides -> LCA is root
assertEquals("LCA balanced AVL 2,13 = 4", 4, tree.findLCA(2, 13).getVal());
//both elements are in the tree on same side and same branch -> one is parent of the other and also the LCA
assertEquals("LCA balanced AVL 2,1 = 2", 2, tree.findLCA(2, 1).getVal());
//both elements are in the tree on same side but different branches -> one is parent of the other and also the LCA
assertEquals("LCA balanced AVL 20,6 = 4", 13, tree.findLCA(20, 6).getVal());
//same non-root element -> LCA is the element itself
assertEquals("LCA balanced AVL 33,33 = 0", 33, tree.findLCA(33, 33).getVal());
//same root element -> LCA is the element itself and also the root
assertEquals("LCA balanced AVL 13,13 = 0", 13, tree.findLCA(13, 13).getVal());
input = new int[]{13, 13, 13};
tree = BST.buildBalancedAVL(input);
//same duplicate element -> LCA is the element itself and also the root
assertEquals("LCA duplicate balanced AVL 13,13 = 13", 13, tree.findLCA(13, 13).getVal());
}
@Test
//distance of two elements in tree with lowest common ancestor logic
public void distanceWLCA() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
//one element does not exist in the tree
assertEquals("Distance with LCA 4,56 = -1", -1, tree.distanceWLCA(4, 56));
//neither element exists in the tree
assertEquals("Distance with LCA 32,56 = -1", -1, tree.distanceWLCA(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance with LCA 4,18 = 5", 5, tree.distanceWLCA(4, 18));
//both elements are in the tree on same side and same branch
assertEquals("Distance with LCA 2,1 = 1", 1, tree.distanceWLCA(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance with LCA 2,4 = 2", 2, tree.distanceWLCA(2, 4));
//same non-root element
assertEquals("Distance with LCA 33,33 = 0", 0, tree.distanceWLCA(33, 33));
//same root element
assertEquals("Distance with LCA 13,13 = 0", 0, tree.distanceWLCA(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildUnbalanced(input);
//same duplicate element
assertEquals("Distance duplicate with LCA 13,13 = 0", 0, tree.distanceWLCA(13, 13));
//with parent, we expect no different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//one element does not exist in the tree
assertEquals("Distance with parent with LCA 4,56 = -1", -1, tree.distanceWLCA(4, 56));
//neither element exists in the tree
assertEquals("Distance with parent with LCA 32,56 = -1", -1, tree.distanceWLCA(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance with parent with LCA 4,18 = 5", 5, tree.distanceWLCA(4, 18));
//both elements are in the tree on same side and same branch
assertEquals("Distance with parent with LCA 2,1 = 1", 1, tree.distanceWLCA(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance with parent with LCA 2,4 = 2", 2, tree.distanceWLCA(2, 4));
//same non-root element
assertEquals("Distance with parent with LCA 33,33 = 0", 0, tree.distanceWLCA(33, 33));
//same root element
assertEquals("Distance with parent with LCA 13,13 = 0", 0, tree.distanceWLCA(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildUnbalancedWParent(input);
//same duplicate element
assertEquals("Distance duplicate with parent with LCA 13,13 = 0", 0, tree.distanceWLCA(13, 13));
//with balanced AVL, we expect different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
//one element does not exist in the tree
assertEquals("Distance balanced AVL with LCA 4,56 = -1", -1, tree.distanceWLCA(4, 56));
//neither element exists in the tree
assertEquals("Distance balanced AVL with LCA 32,56 = -1", -1, tree.distanceWLCA(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance balanced AVL with LCA 2,13 = 2", 2, tree.distanceWLCA(2, 13));
//both elements are in the tree on same side and same branch
assertEquals("Distance balanced AVL with LCA 2,1 = 1", 1, tree.distanceWLCA(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance balanced AVL with LCA 20,6 = 2", 2, tree.distanceWLCA(20, 6));
//same non-root element
assertEquals("Distance balanced AVL with LCA 33,33 = 0", 0, tree.distanceWLCA(33, 33));
//same root element
assertEquals("Distance balanced AVL with LCA 13,13 = 0", 0, tree.distanceWLCA(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildBalancedAVL(input);
//same duplicate element
assertEquals("Distance duplicate balanced AVL with LCA 13,13 = 0", 0, tree.distanceWLCA(13, 13));
}
@Test
//distance of two elements in tree with parent pointers
public void distanceWParent() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//one element does not exist in the tree
assertEquals("Distance with parent 4,56 = -1", -1, tree.distanceWParent(4, 56));
//neither element exists in the tree
assertEquals("Distance with parent 32,56 = -1", -1, tree.distanceWParent(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance with parent 4,18 = 5", 5, tree.distanceWParent(4, 18));
//both elements are in the tree on same side and same branch
assertEquals("Distance with parent 2,1 = 1", 1, tree.distanceWParent(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance with parent 2,4 = 2", 2, tree.distanceWParent(2, 4));
//same non-root element
assertEquals("Distance with parent 33,33 = 0", 0, tree.distanceWParent(33, 33));
//same root element
assertEquals("Distance with parent 13,13 = 0", 0, tree.distanceWParent(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildUnbalancedWParent(input);
//same duplicate element
assertEquals("Distance duplicate with parent 13,13 = 0", 0, tree.distanceWParent(13, 13));
//with balanced AVL, we expect different behaviour
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
//one element does not exist in the tree
assertEquals("Distance balanced AVL with parent 4,56 = -1", -1, tree.distanceWParent(4, 56));
//neither element exists in the tree
assertEquals("Distance balanced AVL with parent 32,56 = -1", -1, tree.distanceWParent(32, 56));
//both elements are in the tree on different sides
assertEquals("Distance balanced AVL with parent 2,13 = 2", 2, tree.distanceWParent(2, 13));
//both elements are in the tree on same side and same branch
assertEquals("Distance balanced AVL with parent 2,1 = 1", 1, tree.distanceWParent(2, 1));
//both elements are in the tree on same side but different branches
assertEquals("Distance balanced AVL with parent 20,6 = 2", 2, tree.distanceWParent(20, 6));
//same non-root element
assertEquals("Distance balanced AVL with parent 33,33 = 0", 0, tree.distanceWParent(33, 33));
//same root element
assertEquals("Distance balanced AVL with parent 13,13 = 0", 0, tree.distanceWParent(13, 13));
input = new int[]{13, 13, 13};
tree = BST.buildBalancedAVL(input);
//same duplicate element
assertEquals("Distance duplicate balanced AVL with parent 13,13 = 0", 0, tree.distanceWParent(13, 13));
}
@Test
//preorder visit
public void preorderVisit() {
//empty
input = null;
tree = BST.buildUnbalanced(input);
preorder = BSTUtils.preorderVisit(tree);
output = null;
assertArrayEquals("preorder visit null", output, preorder);
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
preorder = BSTUtils.preorderVisit(tree);
output = new int[]{1};
assertArrayEquals("preorder visit 1", output, preorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
preorder = BSTUtils.preorderVisit(tree);
output = new int[]{13, 2, 1, 6, 4, 33, 18, 20};
assertArrayEquals("preorder visit 13, 2, 1, 6, 4, 33, 18, 20", output, preorder);
//with balanced AVL, we expect different behaviour
//empty
input = null;
tree = BST.buildBalancedAVL(input);
preorder = BSTUtils.preorderVisit(tree);
output = null;
assertArrayEquals("preorder visit balanced AVL null", output, preorder);
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
preorder = BSTUtils.preorderVisit(tree);
output = new int[]{1};
assertArrayEquals("preorder visit balanced AVL 1", output, preorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
preorder = BSTUtils.preorderVisit(tree);
output = new int[]{4, 2, 1, 13, 6, 20, 18, 33};
assertArrayEquals("preorder visit balanced AVL 4, 2, 1, 13, 6, 20, 18, 33", output, preorder);
}
@Test
//inorder visit
public void inorderVisit() {
//empty
input = null;
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisit(tree);
output = null;
assertArrayEquals("inorder visit null", output, inorder);
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisit(tree);
output = new int[]{1};
assertArrayEquals("inorder visit 1", output, inorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisit(tree);
output = new int[]{1, 2, 4, 6, 13, 18, 20, 33};
assertArrayEquals("inorder visit 1, 2, 4, 6, 13, 18, 20, 33", output, inorder);
//with balanced AVL, we expect no different behaviour -> INORDER visit means output is sorted tree!
//empty
input = null;
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisit(tree);
output = null;
assertArrayEquals("inorder visit balanced AVL null", output, inorder);
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisit(tree);
output = new int[]{1};
assertArrayEquals("inorder visit balanced AVL 1", output, inorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisit(tree);
output = new int[]{1, 2, 4, 6, 13, 18, 20, 33};
assertArrayEquals("inorder visit balanced AVL 1, 2, 4, 6, 13, 18, 20, 33", output, inorder);
}
@Test
//inorder visit iterative
public void inorderVisitIterative() {
//empty
input = null;
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisitIterative(tree);
output = null;
assertArrayEquals("inorder visit null", output, inorder);
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisitIterative(tree);
output = new int[]{1};
assertArrayEquals("inorder visit 1", output, inorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisitIterative(tree);
output = new int[]{1, 2, 4, 6, 13, 18, 20, 33};
assertArrayEquals("inorder visit 1, 2, 4, 6, 13, 18, 20, 33", output, inorder);
//with balanced AVL, we expect no different behaviour -> INORDER visit means output is sorted tree!
//empty
input = null;
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisitIterative(tree);
output = null;
assertArrayEquals("inorder visit balanced AVL null", output, inorder);
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisitIterative(tree);
output = new int[]{1};
assertArrayEquals("inorder visit balanced AVL 1", output, inorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisitIterative(tree);
output = new int[]{1, 2, 4, 6, 13, 18, 20, 33};
assertArrayEquals("inorder visit balanced AVL 1, 2, 4, 6, 13, 18, 20, 33", output, inorder);
}
@Test
//postorder visit
public void postorderVisit() {
//empty
input = null;
tree = BST.buildUnbalanced(input);
postorder = BSTUtils.postorderVisit(tree);
output = null;
assertArrayEquals("postorder visit null", output, postorder);
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
postorder = BSTUtils.postorderVisit(tree);
output = new int[]{1};
assertArrayEquals("postorder visit 1", output, postorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
postorder = BSTUtils.postorderVisit(tree);
output = new int[]{1, 4, 6, 2, 20, 18, 33, 13};
assertArrayEquals("postorder visit 1, 4, 6, 2, 20, 18, 33, 13", output, postorder);
//with balanced AVL, we expect different behaviour
//empty
input = null;
tree = BST.buildBalancedAVL(input);
postorder = BSTUtils.postorderVisit(tree);
output = null;
assertArrayEquals("postorder visit balanced AVL null", output, postorder);
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
postorder = BSTUtils.postorderVisit(tree);
output = new int[]{1};
assertArrayEquals("postorder visit balanced AVL 1", output, postorder);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
postorder = BSTUtils.postorderVisit(tree);
output = new int[]{1, 2, 6, 18, 33, 20, 13, 4};
assertArrayEquals("postorder visit balanced AVL 1, 2, 6, 18, 33, 20, 13, 4", output, postorder);
}
@Test
//BFS visit
public void BFSVisit() {
//empty
input = null;
tree = BST.buildUnbalanced(input);
bfs = BSTUtils.BFSVisit(tree);
output = null;
assertArrayEquals("bfs visit null", output, bfs);
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
bfs = BSTUtils.BFSVisit(tree);
output = new int[]{1};
assertArrayEquals("bfs visit 1", output, bfs);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
bfs = BSTUtils.BFSVisit(tree);
output = new int[]{13, 2, 33, 1, 6, 18, 4, 20};
assertArrayEquals("bfs visit 13, 2, 33, 1, 6, 18, 4, 20", output, bfs);
//with balanced AVL, we expect different behaviour
//empty
input = null;
tree = BST.buildBalancedAVL(input);
bfs = BSTUtils.BFSVisit(tree);
output = null;
assertArrayEquals("bfs visit balanced AVL null", output, bfs);
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
bfs = BSTUtils.BFSVisit(tree);
output = new int[]{1};
assertArrayEquals("bfs visit balanced AVL 1", output, bfs);
//generic
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
bfs = BSTUtils.BFSVisit(tree);
output = new int[]{4, 2, 13, 1, 6, 20, 18, 33};
assertArrayEquals("bfs visit balanced AVL 4, 2, 13, 1, 6, 20, 18, 33", output, bfs);
}
@Test
//build tree from preorder + inorder visits
public void buildTreeFromVisit() {
//empty
input = null;
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisit(tree);
preorder = BSTUtils.preorderVisit(tree);
output = BSTUtils.BFSVisit(tree);
tree = BSTUtils.buildTreeFromVisit(preorder, inorder);
bfs = BSTUtils.BFSVisit(tree);
assertArrayEquals("build visit null", output, bfs);
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisit(tree);
preorder = BSTUtils.preorderVisit(tree);
output = BSTUtils.BFSVisit(tree);
tree = BSTUtils.buildTreeFromVisit(preorder, inorder);
bfs = BSTUtils.BFSVisit(tree);
assertArrayEquals("build visit 1", output, bfs);
//generic. BFS on start and reconstructed tree must be equal
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalanced(input);
inorder = BSTUtils.inorderVisit(tree);
preorder = BSTUtils.preorderVisit(tree);
output = BSTUtils.BFSVisit(tree);
tree = BSTUtils.buildTreeFromVisit(preorder, inorder);
bfs = BSTUtils.BFSVisit(tree);
assertArrayEquals("build visit 13, 2, 33, 1, 6, 18, 4, 20", output, bfs);
//with balanced AVL, we expect no different behaviour
//empty
input = null;
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisit(tree);
preorder = BSTUtils.preorderVisit(tree);
output = BSTUtils.BFSVisit(tree);
tree = BSTUtils.buildTreeFromVisit(preorder, inorder);
bfs = BSTUtils.BFSVisit(tree);
assertArrayEquals("build visit balanced AVL null", output, bfs);
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisit(tree);
preorder = BSTUtils.preorderVisit(tree);
output = BSTUtils.BFSVisit(tree);
tree = BSTUtils.buildTreeFromVisit(preorder, inorder);
bfs = BSTUtils.BFSVisit(tree);
assertArrayEquals("build visit balanced AVL 1", output, bfs);
//generic. BFS on start and reconstructed tree must be equal
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildBalancedAVL(input);
inorder = BSTUtils.inorderVisit(tree);
preorder = BSTUtils.preorderVisit(tree);
output = BSTUtils.BFSVisit(tree);
tree = BSTUtils.buildTreeFromVisit(preorder, inorder);
bfs = BSTUtils.BFSVisit(tree);
assertArrayEquals("build visit balanced AVL 13, 4, 20, 2, 6, 18, 33, 1", output, bfs);
}
@Test
//tree depth
public void getTreeDepth() {
//empty
tree = null;
depth = -1;
assertEquals("null tree depth -1", depth, BSTUtils.getTreeDepth(tree));
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
depth = 0;
assertEquals("only root tree depth 0", depth, BSTUtils.getTreeDepth(tree));
//generic, unbalanced
input = new int[]{13, 2, 33, 6, 4, 1, 18};
tree = BST.buildUnbalanced(input);
depth = 3;
assertEquals("unbalanced tree depth 3", depth, BSTUtils.getTreeDepth(tree));
//generic, balanced. Simply pass the elements in order to build it balanced
input = new int[]{33, 15, 50, 1, 16, 45, 60};
tree = BST.buildUnbalanced(input);
depth = 2;
assertEquals("balanced tree depth 2", depth, BSTUtils.getTreeDepth(tree));
//with balanced AVL, we expect different behaviour because the tree is self balancing!
//empty
tree = null;
depth = -1;
assertEquals("null tree balanced AVL depth -1", depth, BSTUtils.getTreeDepth(tree));
//one element
input = new int[]{1};
tree = BST.buildBalancedAVL(input);
depth = 0;
assertEquals("only root tree balanced AVL depth 0", depth, BSTUtils.getTreeDepth(tree));
//generic, unbalanced input, tree will balance itself at each step!
input = new int[]{13, 2, 33, 6, 4, 1, 18};
tree = BST.buildBalancedAVL(input);
depth = 3;
assertEquals("unbalanced input tree balanced AVL depth 3", depth, BSTUtils.getTreeDepth(tree));
//generic, balanced input passed in non balanced order, tree will balance itself at each step!
input = new int[]{50, 15, 1, 33, 60, 16, 45};
tree = BST.buildBalancedAVL(input);
depth = 2;
assertEquals("balanced input tree balanced AVL depth 2", depth, BSTUtils.getTreeDepth(tree));
}
@Test
//tree is balanced
public void isTreeBalanced() {
//empty
tree = null;
isBalanced = true;
assertEquals("null tree is balanced", isBalanced, BSTUtils.isTreeBalanced(tree));
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
isBalanced = true;
assertEquals("single node tree is balanced", isBalanced, BSTUtils.isTreeBalanced(tree));
//generic, unbalanced
input = new int[]{13, 2, 33, 6, 4, 1}; //left depth = 4, right depth = 2
tree = BST.buildUnbalanced(input);
isBalanced = false;
assertEquals("unbalanced tree is not balanced", isBalanced, BSTUtils.isTreeBalanced(tree));
//generic, balanced. Simply pass the elements in order to build it balanced
input = new int[]{33, 15, 50, 1, 16, 45, 60};
tree = BST.buildUnbalanced(input);
isBalanced = true;
assertEquals("balanced tree is balanced", isBalanced, BSTUtils.isTreeBalanced(tree));
//balanced AVL, we expect it to be balanced
input = new int[]{13, 2, 33, 6, 4, 1}; //unbalanced left depth = 4, right depth = 2
tree = BST.buildBalancedAVL(input);
isBalanced = true;
assertEquals("unbalanced input tree balanced AVL is balanced", isBalanced, BSTUtils.isTreeBalanced(tree));
}
@Test
//tree is complete
public void isTreeComplete() {
//empty
tree = null;
isComplete = true;
assertEquals("null tree is complete", isComplete, BSTUtils.isTreeComplete(tree));
//one element
input = new int[]{1};
tree = BST.buildUnbalanced(input);
isComplete = true;
assertEquals("one elment tree is complete", isComplete, BSTUtils.isTreeComplete(tree));
//generic, non complete, only right children
input = new int[]{13, 33, 44};
tree = BST.buildUnbalanced(input);
isComplete = false;
//generic, non complete. All children at same level with a hole in level + 1
input = new int[]{33, 15, 50, 1, 60};
tree = BST.buildUnbalanced(input);
isComplete = false;
assertEquals("complete tree with only 1 more level is complete", isComplete, BSTUtils.isTreeComplete(tree));
assertEquals("oly right childre tree is not complete", isComplete, BSTUtils.isTreeComplete(tree));
//generic, complete. All children at same level
input = new int[]{33, 15, 50};
tree = BST.buildUnbalanced(input);
isComplete = true;
assertEquals("complete tree is complete", isComplete, BSTUtils.isTreeComplete(tree));
//generic, complete. All children at same level with only one left children at level + 1
input = new int[]{33, 15, 50, 1};
tree = BST.buildUnbalanced(input);
isComplete = true;
assertEquals("complete tree with only 1 more level is complete", isComplete, BSTUtils.isTreeComplete(tree));
}
@Test
//second largest element
public void getSecondLargestElement() {
//one element
input = new int[]{1};
tree = BST.buildUnbalancedWParent(input);
node = null;
assertEquals("one element tree has no second largest item", node, tree.getSecondLargestElement());
//two elements right
input = new int[]{1, 2};
tree = BST.buildUnbalancedWParent(input);
val = 1;
assertEquals("two elements right tree expected 1", val, tree.getSecondLargestElement().getVal());
//two elements left
input = new int[]{2, 1};
tree = BST.buildUnbalancedWParent(input);
val = 1;
assertEquals("two elements left tree expected 1", val, tree.getSecondLargestElement().getVal());
//only right children
input = new int[]{13, 33, 44};
tree = BST.buildUnbalancedWParent(input);
val = 33;
assertEquals("only right children expected 33", val, tree.getSecondLargestElement().getVal());
//only left children
input = new int[]{50, 30, 10};
tree = BST.buildUnbalancedWParent(input);
val = 30;
assertEquals("only left children expected 30", val, tree.getSecondLargestElement().getVal());
//generic unbalanced
input = new int[]{13, 2, 33, 6, 4, 1};
tree = BST.buildUnbalancedWParent(input);
val = 13;
assertEquals("generic unbalanced expected 13", val, tree.getSecondLargestElement().getVal());
//generic balanced. Simply pass the elements in order to build it balanced
input = new int[]{33, 15, 50, 1, 16, 45, 60};
tree = BST.buildUnbalancedWParent(input);
val = 50;
assertEquals("generic balanced expected 50", val, tree.getSecondLargestElement().getVal());
//balanced AVL
input = new int[]{13, 2, 33, 6, 4, 1};
tree = BST.buildBalancedAVL(input);
val = 13;
assertEquals("AVL balanced expected 13", val, tree.getSecondLargestElement().getVal());
}
@Test
public void isValidBST(){
tree = null;
assertTrue("null tree is valid BST inorder", BSTUtils.isValidBSTWithInorderVisit(tree));
input = new int[]{1};
tree = BST.buildUnbalanced(input);
assertTrue("tree with only one node is valid BST", tree.isValidBST());
assertTrue("tree with only one node is valid BST inorder", BSTUtils.isValidBSTWithInorderVisit(tree));
input = new int[]{1, 2, 3};
tree = BST.buildUnbalanced(input);
assertTrue("increasing tree is valid BST", tree.isValidBST());
assertTrue("increasing tree is valid BST inorder", BSTUtils.isValidBSTWithInorderVisit(tree));
input = new int[]{3, 2, 1};
tree = BST.buildUnbalanced(input);
assertTrue("decreasing tree is valid BST", tree.isValidBST());
assertTrue("decreasing tree is valid BST inorder", BSTUtils.isValidBSTWithInorderVisit(tree));
input = new int[]{5, 2, 7, 1, 3, 6, 8};
tree = BST.buildUnbalanced(input);
assertTrue("valid tree is valid BST", tree.isValidBST());
assertTrue("valid tree is valid BST inorder", BSTUtils.isValidBSTWithInorderVisit(tree));
//to build an invalid BST we must do it ourselves since our builder functions force the correct logic.
//4 should NOT be in the right subtree of root 5
input = new int[]{5, 2, 7, 1, 3, 4, 8};
tree = new BST(5);
BST left = tree.addLeft(2);
left.addLeft(1);
left.addRight(3);
BST right = tree.addRight(7);
right.addLeft(4);
right.addRight(8);
assertFalse("invalid tree is not valid BST", tree.isValidBST());
assertFalse("invalid tree is not valid BST inorder", BSTUtils.isValidBSTWithInorderVisit(tree));
}
}
Raw
BSTLockJTests.java
package com.blogspot.groglogs.test.bst;
import org.junit.Test;
import com.blogspot.groglogs.bst.BST;
import com.blogspot.groglogs.bst.BSTUtils;
import java.util.List;
import static org.junit.Assert.*;
public class BSTLockJTests {
int[] input;
BST tree = null;
List<BST> leaves;
@Test
//we can lock all leaves, but no other nodes
public void lockLeaves() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//gather all the leaves
leaves = BSTUtils.getLeaves(tree);
//test each leaf is not locked, then lock it
for(BST node : leaves){
assertEquals("Leaf is not locked yet", false, node.isLocked());
//lock this leaf
assertEquals("Locking leaf", true, node.lock());
assertEquals("Leaf is now locked", true, node.isLocked());
}
//try to lock again the same leaf unsuccessfully
for(BST node : leaves){
assertEquals("Locking leaf again", false, node.lock());
}
//try to lock the root unsuccessfully
assertEquals("Locking root with locked leaf", false, tree.lock());
assertEquals("Root with locked leaf is not locked", false, tree.isLocked());
//try to lock the root left unsuccessfully
assertEquals("Locking root.left with locked leaf", false, tree.left.lock());
assertEquals("Root.left with locked leaf is not locked", false, tree.left.isLocked());
//try to lock the root right child unsuccessfully
assertEquals("Locking root.right with locked leaf", false, tree.right.lock());
assertEquals("Root.right with locked leaf is not locked", false, tree.right.isLocked());
//try to unlock the root, then lock it unsuccessfully
tree.unlock();
assertEquals("Unlocking root with locked leaf", false, tree.isLocked());
tree.lock();
assertEquals("Locking root after unlock with locked leaf", false, tree.isLocked());
//try to unlock the root.left, then lock it unsuccessfully
tree.left.unlock();
assertEquals("Unlocking root.left with locked leaf", false, tree.left.isLocked());
tree.left.lock();
assertEquals("Locking root.left after unlock with locked leaf", false, tree.left.isLocked());
//try to unlock the root.right, then lock it unsuccessfully
tree.right.unlock();
assertEquals("Unlocking root.right with locked leaf", false, tree.right.isLocked());
tree.right.lock();
assertEquals("Locking root.right after unlock with locked leaf", false, tree.right.isLocked());
//test each leaf is still locked, then unlock it
for(BST node : leaves){
assertEquals("Leaf is still locked", true, node.isLocked());
//unlock this leaf
node.unlock();
assertEquals("Leaf is now unlocked", false, node.isLocked());
}
//try to unlock each leaf again successfully
for(BST node : leaves){
node.unlock();
assertEquals("Leaf is still unlocked", false, node.isLocked());
}
//try to unlock the root successfully
tree.unlock();
assertEquals("Unlocking root with unlocked leaf", false, tree.isLocked());
//try to unlock the root left successfully
tree.left.unlock();
assertEquals("Unlocking root.left with unlocked leaf", false, tree.left.isLocked());
//try to unlock the root right child successfully
tree.right.unlock();
assertEquals("Unlocking root.right with unlocked leaf", false, tree.right.isLocked());
}
@Test
//we can lock the root and no other node
public void lockRoot() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//gather all the leaves
leaves = BSTUtils.getLeaves(tree);
//lock the root
assertEquals("Root is not locked yet", false, tree.isLocked());
//lock the root
assertEquals("Locking root", true, tree.lock());
assertEquals("Root is now locked", true, tree.isLocked());
//test each leaf is not locked, then try to lock it unsuccessfully
for(BST node : leaves){
assertEquals("Leaf is not locked yet", false, node.isLocked());
//lock this leaf
assertEquals("Locking leaf", false, node.lock());
assertEquals("Leaf is still not locked", false, node.isLocked());
}
//unlock each leaf, then try to lock it unsuccessfully
for(BST node : leaves){
//unlock this leaf
node.unlock();
assertEquals("Leaf after unlock is not locked", false, node.isLocked());
//we still cannot lock this leaf because the root is locked
assertEquals("Leaf cannot be locked", false, node.lock());
}
}
@Test
//we can lock the root.right and root.left and no other node
public void lockMid() {
input = new int[]{13, 2, 33, 6, 4, 1, 18, 20};
tree = BST.buildUnbalancedWParent(input);
//gather all the leaves
leaves = BSTUtils.getLeaves(tree);
//lock the root.left
assertEquals("Root.right is not locked yet", false, tree.left.isLocked());
//lock the root.left
assertEquals("Locking root.left", true, tree.left.lock());
assertEquals("Root.left is now locked", true, tree.left.isLocked());
//lock the root.right
assertEquals("Root.right is not locked yet", false, tree.right.isLocked());
//lock the root.right
assertEquals("Locking root.right", true, tree.right.lock());
assertEquals("Root.right is now locked", true, tree.right.isLocked());
//try to lock the root unsuccessfully
assertEquals("Root is not locked yet", false, tree.isLocked());
//lock the root
assertEquals("Locking root", false, tree.lock());
assertEquals("Root is still not locked", false, tree.isLocked());
//unlock the root, then try to lock it unsuccessfully
tree.unlock();
assertEquals("Locking root after unlock", false, tree.lock());
assertEquals("Root after unlock is still not locked", false, tree.isLocked());
//test each leaf is not locked, then try to lock it unsuccessfully
for(BST node : leaves){
assertEquals("Leaf is not locked yet", false, node.isLocked());
//lock this leaf
assertEquals("Locking leaf", false, node.lock());
assertEquals("Leaf is still not locked", false, node.isLocked());
}
//unlock each leaf, then try to lock it unsuccessfully
for(BST node : leaves){
//unlock this leaf
node.unlock();
assertEquals("Leaf after unlock is not locked", false, node.isLocked());
//we still cannot lock this leaf because the root is locked
assertEquals("Leaf cannot be locked", false, node.lock());
}
}
}
Raw
BSTUtils.java
package com.blogspot.groglogs.bst;
import com.blogspot.groglogs.bst.structures.BST;
import com.blogspot.groglogs.bst.structures.Entry;
import com.blogspot.groglogs.bst.structures.Pair;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
public class BSTUtils {
//used in serializeBST and deserializeBST
private final static String VAL_SEP = ",", NULL_VAL = "X";
/*
preorder visit: root, left, right
inorder visit: left, root, right
postorder visit: left, right, root
*/
private static List<Integer> doPreorderVisit(BST root, List<Integer> out){
if(root != null){
out.add(root.getVal());
doPreorderVisit(root.left, out);
doPreorderVisit(root.right, out);
}
return out;
}
public static List<Integer> preorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);
return out;
}
public static int[] preorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
private static List<Integer> doInorderVisit(BST root, List<Integer> out){
if(root != null){
doInorderVisit(root.left, out);
out.add(root.getVal());
doInorderVisit(root.right, out);
}
return out;
}
public static List<Integer> inorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);
return out;
}
public static int[] inorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
//iterative inorder visit, use a stack as helper structure
private static List<Integer> doInorderVisitIterative(BST root, List<Integer> out){
if(root == null) return out;
BST curr = root;
Stack<BST> s = new Stack<>();
//keep looping as long as we have at least one valid element
while(!s.isEmpty() || curr != null){
//if current element is not null, keep stacking the left children
if(curr != null){
s.push(curr);
curr = curr.left;
}
//when we get a null, move up the tree (in stack view) again, visit the node, and switch to the right subtree
else{
curr = s.pop();
out.add(curr.getVal());
curr = curr.right;
}
}
return out;
}
public static List<Integer> inorderVisitListIterative(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisitIterative(root, out);
return out;
}
public static int[] inorderVisitIterative(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisitIterative(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
private static List<Integer> doPostorderVisit(BST root, List<Integer> out){
if(root != null){
doPostorderVisit(root.left, out);
doPostorderVisit(root.right, out);
out.add(root.getVal());
}
return out;
}
public static List<Integer> postorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);
return out;
}
public static int[] postorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
public static List<Integer> BFSVisitList(BST root){
if(root == null) return null;
List<Integer> out = new ArrayList<>();
Queue<BST> q = new LinkedList<BST>();
q.add(root);
while(!q.isEmpty()){
BST t = q.remove();
out.add(t.getVal());
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
return out;
}
public static int[] BFSVisit(BST root){
if(root == null) return null;
int[] res = null;
List<Integer> out = BFSVisitList(root);
if(out != null) res = out.stream().mapToInt(i -> i).toArray();
return res;
}
/*
We can build a Binary Tree from its preorder and inorder visits as such:
- in the preorder at position 0 we have the root
- in the inorder before the index of the root found at previous step, we have the left subtree and after we have the right subtree
- we can determine a range to search for our elements inside and recursively compute the left and right subtrees for each subroot
CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays
However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object
*/
private static BST doBuild(int[] preorder, int[] inorder, int start, int end, int root_idx, Map<Integer, Integer> in_map){
if(end <= start) return null; //this is the child of a leaf
BST t = new BST(preorder[root_idx]); //add ourselves as root
//find this root in the inorder visit
int subroot_idx = in_map.get(preorder[root_idx]);
/*
the left subtree should search for the root immediately adjacent the current one in the preorder visit (root_idx + 1)
it should search for the rest of the subtree in the portion between our start and the current subroot (start to subroot_idx) in the inorder visit
*/
t.setLeft(doBuild(preorder, inorder, start, subroot_idx, root_idx + 1, in_map));
/*
the right subtree should search for the root immediately adjacent the last left subtree element we checked in the preorder visit (root_idx + 1 + subroot_idx - start)
it should search for the rest of the subtree in the portion between our current subroot and the our end (subroot_idx + 1 to end) in the inorder visit
*/
t.setRight(doBuild(preorder, inorder, subroot_idx + 1, end, root_idx + 1 + subroot_idx - start, in_map));
return t;
}
public static BST buildTreeFromVisit(int[] preorder, int[] inorder){
if(preorder == null || inorder == null || preorder.length != inorder.length) return null;
/*
with this we bring time down from O(N^2) to O(N) and are still in O(N) space
Map from value to index in array
*/
HashMap<Integer, Integer> in_map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
in_map.put(inorder[i], i);
}
BST out = doBuild(preorder, inorder, 0, preorder.length, 0, in_map);
return out;
}
//find depth of the tree
public static int getTreeDepth(BST root){
if(root == null) return -1;
return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;
}
/*
is tree balanced
A tree is balanced if the left and right branches do not differ for more than 1 level in length
*/
private static Entry isTreeBalancedAux(BST root){
//null root is always balanced
if(root == null) return new Entry(true, -1);
Entry left, right;
//check subtrees
left = isTreeBalancedAux(root.left);
right = isTreeBalancedAux(root.right);
//if they are not balanced, we have our answer
if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);
//otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced
if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);
//finally, if all is good, return the max depth from this node including itself and mark it as balanced
return new Entry(true, Math.max(left.height, right.height) + 1);
}
public static boolean isTreeBalanced(BST root){
return isTreeBalancedAux(root).isBalanced;
}
/*
is tree complete
A tree is complete if for each level, there are no holes between children:
complete =
A
B C
no holes between B and C
complete =
A
B
no holes after B
non complete =
A
C
hole before C
*/
public static boolean isTreeComplete(BST root){
//null root is always complete
if(root == null) return true;
/*
otherwise, we must NOT have null nodes between two nodes at each level
so do a BFS BUT CAUTION: track also NULL children, then check we do not have a non null node after we encountered a null one
*/
Queue<BST> levels = new LinkedList<>();
boolean has_null = false;
levels.add(root);
while(!levels.isEmpty()){
BST t = levels.remove();
//if current node is not null
if(t != null) {
//if we had a null, fail
if(has_null) return false;
//otherwise add its children
levels.add(t.left);
levels.add(t.right);
}
//track if the node we just saw was null. CAUTION: do not overwrite it!
has_null = has_null || t == null;
}
//if we navigated the whole tree without problem, it is complete
return true;
}
//helper for getLeaves
public static List<BST> gatherLeaves(BST node, List<BST> out){
if(node != null){
//if we are a leaf, add us to the result
if(node.left == null && node.right == null) out.add(node);
gatherLeaves(node.left, out);
gatherLeaves(node.right, out);
}
return out;
}
//gather all the tree leaves in a list
public static List<BST> getLeaves(BST node){
if(node == null) return null;
return gatherLeaves(node, new LinkedList<>());
}
//is a list of nodes equal
public static boolean isEqualNodeList(List<BST> nodeList, List<BST> otherNodeList){
if(nodeList == null) return otherNodeList == null;
if(otherNodeList == null) return false;
if(nodeList.size() != otherNodeList.size()) return false;
for(int i = 0; i < nodeList.size(); i++){
if(nodeList.get(i).val != otherNodeList.get(i).val) return false;
}
return true;
}
/**
* Verifies whether this tree is a valid BST using a inorder visit.
* When inserting a node in the tree we move left or right down until we find a spot where to place him.
* Therefore the location of a node is constrained by boundaries set from elements at the previous levels.
* For example a node X can NEVER be in the RIGHT subtree of a node that has a higher value than X.
* The inorder visit gives us the nodes in their natural order, if we find inconsistencies there, the tree is not a valid BST.
* @param t the tree to check.
* @return true if all nodes in this tree respect the BST rule. A null tree is always a valid BST.
*/
public static boolean isValidBSTWithInorderVisit(BST t){
if(t == null){
return true;
}
List<Integer> inorderVisit = doInorderVisit(t, new ArrayList<>());
for(int i = 0; i < inorderVisit.size() - 1; i++){
if(inorderVisit.get(i) > inorderVisit.get(i + 1)){
return false;
}
}
return true;
}
/**
* Given a BST return a string serialization of it. Use comma as value separator and X as marker for nulls.
* @param t the tree to serialize.
* @return the string serialization of the given tree.
*/
public static String serializeBST(BST t){
if(t == null){
return "";
}
StringBuilder sb = new StringBuilder();
int nullsInNextLevel = 0, level = 0, elementsInThisLevel = 0;
Queue<BST> nodes = new LinkedList<>();
nodes.add(t);
/*
Walk on the tree level by level and add values to our string. Also track null children at any level.
We count how many nodes we add to determine at which level of the tree are we. By also handling nulls, we do not
miss any position.
We know we need to stop when the amount of children at the NEXT level that are null equals the maximum amount
of nodes allowed at that level.
*/
while(!nodes.isEmpty()){
//if next level is full of nulls, we are done since we just processed all the leaves
if(nullsInNextLevel == Math.pow(2, level + 1)){
break;
}
//if we processed the maximum amount of elements at this level, we are starting a new level
if(elementsInThisLevel == Math.pow(2, level)){
level++;
elementsInThisLevel = 0;
nullsInNextLevel = 0;
}
BST curr = nodes.poll();
BST left, right;
//if this node is not null, add its value and track its children
if(curr != null){
sb.append(curr.val);
left = curr.left;
right = curr.right;
}
//otherwise add null value and track two fake null children
else {
sb.append(NULL_VAL);
left = null;
right = null;
}
sb.append(VAL_SEP);
elementsInThisLevel++;
//if the children are null, remember that BUT also add them to the queue
if(left == null){
nullsInNextLevel++;
}
nodes.add(left);
if(right == null){
nullsInNextLevel++;
}
nodes.add(right);
}
return sb.toString();
}
/**
* From the given serialization of a BST and a start index, retrieve, if possible, the value of the node in that
* position in the given string.
* @param serializedBST the string representation of the serialized BST.
* @param start the start position in our string where to search the value from.
* @return the value of the node starting at the given position in the string.
* @throws IllegalArgumentException if there is no value (two value separators found adjacent)
* or the given start index is outside of the string boundaries.
*/
private static String getSerializedVal(String serializedBST, int start){
//if we use indexOf and substring we walk the same portion twice
//better approach is to walk and track ourselves all read characters until the marker so we only walk once
StringBuffer sb = new StringBuffer();
for(int i = start; i < serializedBST.length(); i++){
if(serializedBST.charAt(i) == VAL_SEP.charAt(0)){
break;
}
sb.append(serializedBST.charAt(i));
}
if(sb.toString().length() == 0){
throw new IllegalArgumentException("Bad serialization, string");
}
return sb.toString();
}
/**
* Given a serialized value for a BST node, convert it to the corresponding int value.
* @param serializedVal the string representation of a node value. Should be an integer.
* @return the integer corresponding to the serialized node value.
* @throws IllegalArgumentException if the given representation is not a valid integer number.
*/
private static int convertSerializedValToInt(String serializedVal){
try{
return Integer.parseInt(serializedVal);
} catch(NumberFormatException e){
throw new IllegalArgumentException("Invalid value " + serializedVal + " found");
}
}
/**
* Given a string representation of a BST, rebuild the tree corresponding to that serialization.
* @param serializedBST the serialized BST string representation.
* @return the head of the rebuilt BST.
* @throws IllegalArgumentException if the given representation is not a valid BST.
*/
public static BST deserializeBST(String serializedBST){
if(serializedBST == null || serializedBST.length() == 0){
return null;
}
//immediately try to get the root
String serializedVal = getSerializedVal(serializedBST, 0);
BST head = new BST(convertSerializedValToInt(serializedVal));
//we add all nodes to a queue and keep walking the string, each time we expect two children for a node
//if children or node were null, still add them to the queue and simply skip processing them
Queue<BST> nodes = new LinkedList<>();
nodes.add(head);
//track in which position in the serialized string are we after each value read attempt
int stringPosition = serializedVal.length() + 1;
/*
for each node we pop, its two children will be exactly adjacent in the given serialization string starting from
the index where we currently are. If we had null values, we skip them but treat them as nodes with two null
children and add everything to the queue. We stop when the reach the end of the input string.
If there was a problem, it will be raised by the internal logic, otherwise the only nodes left in the queue
will be null markers.
*/
while(!nodes.isEmpty()) {
if(stringPosition >= serializedBST.length()){
break;
}
BST currNode = nodes.poll();
//these portions are identical, could be improved with a function returning a Pair<node, charactersRead>
//attempt to build left child
serializedVal = getSerializedVal(serializedBST, stringPosition);
if(!serializedVal.equals(NULL_VAL)){
currNode.left = new BST(convertSerializedValToInt(serializedVal));
nodes.add(currNode.left);
}
else{
nodes.add(null);
}
stringPosition += serializedVal.length() + 1;
//attempt to build right child
serializedVal = getSerializedVal(serializedBST, stringPosition);
if(!serializedVal.equals(NULL_VAL)){
currNode.right = new BST(convertSerializedValToInt(serializedVal));
nodes.add(currNode.right);
}
else{
nodes.add(null);
}
stringPosition += serializedVal.length() + 1;
}
return head;
}
/**
* Given two BST, checks if they are identical. To be identical, they need to have the exact same values in the exact
* same node positions.
* @param t1 the first tree.
* @param t2 the second tree.
* @return true if the two BSTs are identical.
*/
public static boolean areEqualBST(BST t1, BST t2){
if(t1 == null && t2 == null){
return true;
}
//we just do a parallel BFS on both and break as soon as we find something not matching
if(t1 != null && t2 != null){
Queue<BST> t1Nodes = new LinkedList<>(), t2Nodes = new LinkedList<>();
t1Nodes.add(t1);
t2Nodes.add(t2);
while(!t1Nodes.isEmpty() && !t2Nodes.isEmpty()){
BST t1Node = t1Nodes.poll();
BST t2Node = t2Nodes.poll();
if(t1Node.val != t2Node.val){
return false;
}
//handle nulls in left child
if(t1Node.left != null && t2Node.left !=null){
t1Nodes.add(t1Node.left);
t2Nodes.add(t2Node.left);
}
else{
if(!(t1Node.left == null && t2Node.left ==null)){
return false;
}
}
//handle nulls in right child
if(t1Node.right != null && t2Node.right !=null){
t1Nodes.add(t1Node.right);
t2Nodes.add(t2Node.right);
}
else{
if(!(t1Node.right == null && t2Node.right ==null)){
return false;
}
}
}
//if we broke the loop but one queue is not empty, the trees cannot be identical since one has more elements
if(t1Nodes.isEmpty() && t2Nodes.isEmpty()){
return true;
}
}
return false;
}
/**
* Given a BST, invert it in place. All right children become left and all left children become right.
* @param t the tree to invert.
*/
public static void invertBST(BST t){
if(t == null){
return;
}
/*
Do BFS, we have O(N) extra space for the queue, exactly O(N/2) as worst case is full tree and we add all leaves to the queue
Do DFS or use recursion, we have O(log N) for the stack as worst case is full tree but we process one leaf at a time
so in the stack we only have the path to that leaf, which is at most log N elements
If we use queue and remove from the end, we also have space usage as DFS
*/
BST left = t.left;
t.left = t.right;
t.right = left;
if(t.left != null){
invertBST(t.left);
}
if(t.right != null){
invertBST(t.right);
}
}
//helper for findFloorAndCeil
/*
Walk down the tree setting boundaries each time where the floor and ceil for a specific value would be.
If we find the value, set it as result, otherwise check how to navigate and update floor and ceil accordingly.
When we reach a null (moved out of a leaf) our value is not in the tree so floor and ceil are the last we had.
Our tree is of integers so we use MIN and MAX int as initial values for our bounds.
*/
private static Pair<Integer, Integer> findFloorAndCeil(BST t, int val, int floor, int ceil){
if(t == null){
return new Pair(floor, ceil);
}
if(t.val == val){
return new Pair(val, val);
}
if(t.val > val){
return findFloorAndCeil(t.left, val, floor, t.val);
}
return findFloorAndCeil(t.right, val, t.val, ceil);
}
/**
* Given a BST, find the floor and ceil for a given value, if either does not exist, print them as min or max int.
* If the value is a node, both floor and ceil are that value.
* @param t the tree.
* @param val the value to find floor and ceiling for.
* @return the floor and ceiling for the given value in the tree.
*/
public static Pair<Integer, Integer> findFloorAndCeil(BST t, int val){
if(t == null){
return new Pair<>(Integer.MIN_VALUE, Integer.MAX_VALUE);
}
return findFloorAndCeil(t, val, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
/**
* Given a binary tree, list the values of nodes we would see by looking at it from the right side.
* @param t the tree.
* @return list of values that are the rightmost value of each level in the tree.
*/
public static List<Integer> rightSideView(BST t){
List<Integer> out = new ArrayList<>();
if(t == null){
return out;
}
/*
We do BFS and add a marker to indicate end of a level. We enqueue nodes as a normal BFS.
When we dequeue a node, we check if the next in the queue is the marker, if yes we add this node to the result,
then enqueue its children (if any) and add the marker back ONLY if there were elements left after us.
*/
final BST marker = null;
Queue<BST> q = new LinkedList();
q.add(t);
q.add(marker);
while(!q.isEmpty()){
//process this node and add its children to the queue
BST curr = q.remove();
if(curr.left != null){
q.add(curr.left);
}
if(curr.right != null){
q.add(curr.right);
}
//if the next node is the marker, we are the last on this level, add us to the result
//then remove the marker and add it back to the end of the queue ONLY if there are still elements there
//otherwise we are the very last node in the tree and there is nowhere else to go to continue
if(q.peek() == marker){
out.add(curr.val);
q.remove();
if(!q.isEmpty()){
q.add(marker);
}
}
}
return out;
}
private static boolean isMirror(BST left, BST right){
if(left == null && right == null){
return true;
}
if(left == null || right == null){
return false;
}
if(left.val != right.val){
return false;
}
return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
/**
* Given the root of a binary tree, check whether all nodes are mirrored along a line that runs through the root.
* @param root the root of the tree.
* @return true if all nodes are mirrored along a line that runs through the root.
*/
public static boolean isMirror(BST root){
if(root == null){
return true;
}
/*
Given two children at a certain level, they are correct mirrors if they have same value
and their children are mirrored:
left.left = right.right (outside branches)
left.right = right.left (inside branches)
We can do this recursively
*/
return isMirror(root.left, root.right);
}
//helper for getDeepestNode
private static Pair<Integer, Integer> getDeepestNode(BST t, int depth){
/*
Walk down the tree asking each node to pick the deepest node it has among its children.
If t is null, there is no tree.
If t is a leaf, return itself plus its depth.
Otherwise ask both left and right side, and choose the deepest node of the two.
*/
if(t == null){
return new Pair<>(-1, Integer.MIN_VALUE);
}
if(t.left == null && t.right == null){
return new Pair<>(t.val, depth);
}
Pair<Integer, Integer> left = getDeepestNode(t.left, depth + 1);
Pair<Integer, Integer> right = getDeepestNode(t.right, depth + 1);
if(left.getSecond() > right.getSecond()){
return left;
}
return right;
}
/**
* Given the root of a binary tree, return any deepest node.
* @param t the root of the tree.
* @return one of the deepest nodes.
*/
public static int getDeepestNode(BST t){
return getDeepestNode(t, 0).getFirst();
}
//recursively walk down both children until a given depth is reached
//the add the value for the node at that level to the solution and stop
private static void getAllValuesAtDepth(BST t, int depth, int currDepth, List<Integer> out){
if(t == null){
return;
}
if(currDepth == depth){
out.add(t.val);
return;
}
getAllValuesAtDepth(t.left, depth, currDepth + 1, out);
getAllValuesAtDepth(t.right, depth, currDepth + 1, out);
}
/**
* Given a binary tree, return all nodes at a given depth.
* @param t the tree root.
* @param depth the depth.
* @return all nodes at the given depth.
*/
public static List<Integer> getAllValuesAtDepth(BST t, int depth){
List<Integer> out = new ArrayList<>();
if(t == null || depth < 0){
return out;
}
getAllValuesAtDepth(t, depth, 0, out);
return out;
}
}
Raw
Entry.java
package com.blogspot.groglogs.bst.structures;
public class Entry {
public boolean isBalanced;
public int height;
public Entry(boolean isBalanced, int height){
this.isBalanced = isBalanced;
this.height = height;
}
}
Raw
FindFloorAndCeilJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BSTUtils;
import com.blogspot.groglogs.bst.structures.BST;
import com.blogspot.groglogs.bst.structures.Pair;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class FindFloorAndCeilJTests {
BST in;
int val;
Pair<Integer, Integer> expected;
@Test
public void nullEmpty() {
in = null;
val = 0;
expected = new Pair<>(Integer.MIN_VALUE, Integer.MAX_VALUE);
assertEquals("null tree", expected, BSTUtils.findFloorAndCeil(in, val));
}
@Test
public void valNotInTree() {
in = new BST(2);
in.addLeft(1);
in.addRight(3);
val = 7;
expected = new Pair<>(3, Integer.MAX_VALUE);
assertEquals("val bigger than tree", expected, BSTUtils.findFloorAndCeil(in, val));
in = new BST(2);
in.addLeft(1);
in.addRight(3);
val = 0;
expected = new Pair<>(Integer.MIN_VALUE, 1);
assertEquals("val smaller than tree", expected, BSTUtils.findFloorAndCeil(in, val));
}
@Test
public void valIsNode() {
in = new BST(2);
in.addLeft(1);
in.addRight(3);
val = 3;
expected = new Pair<>(3, 3);
assertEquals("val is right node", expected, BSTUtils.findFloorAndCeil(in, val));
in = new BST(2);
in.addLeft(1);
in.addRight(3);
val = 1;
expected = new Pair<>(1, 1);
assertEquals("val is left node", expected, BSTUtils.findFloorAndCeil(in, val));
in = new BST(2);
in.addLeft(1);
in.addRight(3);
val = 2;
expected = new Pair<>(2, 2);
assertEquals("val is root", expected, BSTUtils.findFloorAndCeil(in, val));
}
@Test
public void valOnLeft() {
/*
10
5 13
1 6 11
*/
in = new BST(10);
in.addLeft(5);
in.addRight(13);
in.left.addLeft(1);
in.left.addRight(6);
in.right.addLeft(11);
val = 4;
expected = new Pair<>(1, 5);
assertEquals("val is on left branch", expected, BSTUtils.findFloorAndCeil(in, val));
/*
8
4 12
2 6 10 14
*/
in = new BST(8);
in.addLeft(4);
in.addRight(12);
in.left.addLeft(2);
in.left.addRight(6);
in.right.addLeft(10);
in.right.addRight(14);
val = 5;
expected = new Pair<>(4, 6);
assertEquals("val is on left branch", expected, BSTUtils.findFloorAndCeil(in, val));
}
}
Raw
GetAllValuesAtDepthJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BSTUtils;
import com.blogspot.groglogs.bst.structures.BST;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class GetAllValuesAtDepthJTests {
BST in;
int depth;
List<Integer> out, expected;
@Test
public void nullEmpty() {
in = null;
depth = 0;
out = BSTUtils.getAllValuesAtDepth(in, depth);
assertTrue("null", out.isEmpty());
}
@Test
public void negativeDepth() {
in = new BST(10);
depth = -1;
out = BSTUtils.getAllValuesAtDepth(in, depth);
assertTrue("negative depth", out.isEmpty());
}
@Test
public void rootOnly() {
in = new BST(10);
depth = 0;
out = BSTUtils.getAllValuesAtDepth(in, depth);
expected = new ArrayList<>();
expected.add(10);
assertEquals("root only", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("values are correct", expected.get(i), out.get(i));
}
in = new BST(10);
in.addRight(11);
in.addLeft(9);
depth = 0;
out = BSTUtils.getAllValuesAtDepth(in, depth);
expected = new ArrayList<>();
expected.add(10);
assertEquals("root only", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("values are correct", expected.get(i), out.get(i));
}
}
@Test
public void firstLevel() {
in = new BST(10);
depth = 1;
out = BSTUtils.getAllValuesAtDepth(in, depth);
assertTrue("root only, depth 1", out.isEmpty());
in = new BST(10);
in.addRight(11);
in.addLeft(9);
depth = 1;
out = BSTUtils.getAllValuesAtDepth(in, depth);
expected = new ArrayList<>();
expected.add(9);
expected.add(11);
assertEquals("first level", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("values are correct", expected.get(i), out.get(i));
}
in = new BST(10);
in.addRight(11);
in.right.addLeft(3);
in.addLeft(9);
in.left.addRight(6);
depth = 1;
out = BSTUtils.getAllValuesAtDepth(in, depth);
expected = new ArrayList<>();
expected.add(9);
expected.add(11);
assertEquals("first level", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("values are correct", expected.get(i), out.get(i));
}
}
@Test
public void sample() {
in = new BST(1);
in.addRight(3);
in.right.addRight(7);
in.addLeft(2);
in.left.addLeft(4);
in.left.addRight(5);
depth = 2;
out = BSTUtils.getAllValuesAtDepth(in, depth);
expected = new ArrayList<>();
expected.add(4);
expected.add(5);
expected.add(7);
assertEquals("first level", expected.size(), out.size());
for (int i = 0; i < expected.size(); i++) {
assertEquals("values are correct", expected.get(i), out.get(i));
}
}
}
Raw
GetDeepestNodeJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BSTUtils;
import com.blogspot.groglogs.bst.structures.BST;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
public class GetDeepestNodeJTests {
BST in;
@Test
public void nullEmpty() {
in = null;
assertEquals("null", -1, BSTUtils.getDeepestNode(in));
}
@Test
public void rootOnly() {
in = new BST(1);
assertEquals("root only", 1, BSTUtils.getDeepestNode(in));
}
@Test
public void twoChildrenSameLevel() {
in = new BST(1);
in.addRight(2);
in.addLeft(3);
assertEquals("two children same level", 2, BSTUtils.getDeepestNode(in));
}
@Test
public void branch() {
in = new BST(1);
BST right = in.addRight(2);
right.addRight(3);
assertEquals("right branch", 3, BSTUtils.getDeepestNode(in));
in = new BST(1);
BST left = in.addLeft(2);
left.addLeft(3);
assertEquals("left branch", 3, BSTUtils.getDeepestNode(in));
}
@Test
public void sample() {
in = new BST(1);
in.addRight(2);
BST left = in.addLeft(3);
left.addLeft(4);
assertEquals("1-3,2-4,x,x,x", 4, BSTUtils.getDeepestNode(in));
in = new BST(1);
in.addRight(2);
left = in.addLeft(3);
left.addRight(4);
assertEquals("1-3,2-x,4,x,x", 4, BSTUtils.getDeepestNode(in));
}
}
Raw
InvertBSTJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BSTUtils;
import com.blogspot.groglogs.bst.structures.BST;
import org.junit.Test;
import static org.junit.Assert.assertTrue;
public class InvertBSTJTests {
BST in, out;
@Test
public void nullEmpty() {
in = null;
out = null;
BSTUtils.invertBST(in);
assertTrue("null tree", BSTUtils.areEqualBST(in, out));
}
@Test
public void oneNode() {
in = new BST(1);
out = new BST(1);
BSTUtils.invertBST(in);
assertTrue("one node", BSTUtils.areEqualBST(in, out));
}
@Test
public void fullRoot() {
in = new BST(1);
in.addLeft(2);
in.addRight(3);
out = new BST(1);
out.addLeft(3);
out.addRight(2);
BSTUtils.invertBST(in);
assertTrue("root with both children", BSTUtils.areEqualBST(in, out));
in = new BST(1);
in.addLeft(2);
out = new BST(1);
out.addRight(2);
BSTUtils.invertBST(in);
assertTrue("root with one children", BSTUtils.areEqualBST(in, out));
}
@Test
public void sample() {
/*
1
2 3
4 5 6
1
3 2
6 5 4
*/
in = new BST(1);
in.addLeft(2);
in.addRight(3);
in.left.addLeft(4);
in.left.addRight(5);
in.right.addLeft(6);
out = new BST(1);
out.addLeft(3);
out.addRight(2);
out.right.addLeft(5);
out.right.addRight(4);
out.left.addRight(6);
BSTUtils.invertBST(in);
assertTrue("sample", BSTUtils.areEqualBST(in, out));
}
}
Raw
IsMirrorJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BSTUtils;
import com.blogspot.groglogs.bst.structures.BST;
import org.junit.Test;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
public class IsMirrorJTests {
BST in;
@Test
public void nullEmpty() {
in = null;
assertTrue("null", BSTUtils.isMirror(in));
}
@Test
public void rootOnly() {
in = new BST(5);
assertTrue("root only", BSTUtils.isMirror(in));
}
@Test
public void oneChild() {
in = new BST(5);
in.addLeft(3);
assertFalse("left child", BSTUtils.isMirror(in));
in = new BST(5);
in.addRight(3);
assertFalse("right child", BSTUtils.isMirror(in));
}
@Test
public void twoChildren() {
in = new BST(5);
in.addLeft(3);
in.addRight(3);
assertTrue("mirror child", BSTUtils.isMirror(in));
in = new BST(5);
in.addRight(3);
in.addLeft(6);
assertFalse("not mirror child", BSTUtils.isMirror(in));
}
@Test
public void sample() {
in = new BST(1);
BST left = in.addLeft(2);
left.addLeft(4);
left.addRight(3);
BST right = in.addRight(2);
right.addLeft(4);
right.addRight(3);
assertFalse("mirror", BSTUtils.isMirror(in));
in = new BST(1);
left = in.addLeft(2);
left.addRight(3);
right = in.addRight(2);
right.addRight(3);
assertFalse("no mirror", BSTUtils.isMirror(in));
}
}
Raw
RightSideViewJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BSTUtils;
import com.blogspot.groglogs.bst.structures.BST;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
public class RightSideViewJTests {
BST head;
List<Integer> out, expected;
@Test
public void nullEmpty() {
head = null;
assertTrue("null tree", BSTUtils.rightSideView(head).isEmpty());
}
@Test
public void allRight() {
head = new BST(1);
head.addRight(2);
head.right.addRight(3);
out = BSTUtils.rightSideView(head);
expected = new ArrayList<>();
expected.add(1);
expected.add(2);
expected.add(3);
assertEquals("all right tree", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("content is correct", expected.get(i), out.get(i));
}
}
@Test
public void allLeft() {
head = new BST(1);
head.addLeft(2);
head.left.addLeft(3);
out = BSTUtils.rightSideView(head);
expected = new ArrayList<>();
expected.add(1);
expected.add(2);
expected.add(3);
assertEquals("all left tree", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("content is correct", expected.get(i), out.get(i));
}
}
@Test
public void hidden() {
head = new BST(1);
head.addLeft(2);
head.addRight(3);
out = BSTUtils.rightSideView(head);
expected = new ArrayList<>();
expected.add(1);
expected.add(3);
assertEquals("hidden node", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("content is correct", expected.get(i), out.get(i));
}
head = new BST(1);
head.addLeft(2);
head.addRight(3);
head.left.addLeft(4);
out = BSTUtils.rightSideView(head);
expected = new ArrayList<>();
expected.add(1);
expected.add(3);
expected.add(4);
assertEquals("hidden node with child", expected.size(), out.size());
for(int i = 0; i < expected.size(); i++){
assertEquals("content is correct", expected.get(i), out.get(i));
}
}
}
Raw
SerializeDeserializeBSTJTests.java
package com.blogspot.groglogs.test.bst;
import com.blogspot.groglogs.bst.BST;
import com.blogspot.groglogs.bst.BSTUtils;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
public class SerializeDeserializeBSTJTests {
BST head, builtHead;
String serialized, builtSerialized;
@Test
public void nullEmptySerialize() {
head = null;
serialized = "";
assertEquals("null tree", serialized, BSTUtils.serializeBST(head));
}
@Test
public void nullEmptyDeserialize() {
serialized = null;
assertNull("null serialized", BSTUtils.deserializeBST(serialized));
serialized = "";
assertNull("empty serialized", BSTUtils.deserializeBST(serialized));
}
@Test(expected = IllegalArgumentException.class)
public void badSerializeThrowsException(){
serialized = "asd";
BSTUtils.deserializeBST(serialized);
}
@Test(expected = IllegalArgumentException.class)
public void badSerializeMissingValueThrowsException(){
serialized = "1,2,,";
BSTUtils.deserializeBST(serialized);
}
@Test(expected = IllegalArgumentException.class)
public void badSerializeUnknownSymbolsThrowsException(){
serialized = "1,2,X,3,asd,4";
BSTUtils.deserializeBST(serialized);
}
@Test
public void onlyRoot() {
head = new BST(1);
serialized = "1,";
builtSerialized = BSTUtils.serializeBST(head);
assertEquals("only root tree serialize", serialized, builtSerialized);
builtHead = BSTUtils.deserializeBST(builtSerialized);
assertEquals("only root tree rebuilt same value", head.getVal(), builtHead.getVal());
assertNull("only root tree rebuilt no left child", builtHead.getLeft());
assertNull("only root tree rebuilt no right child", builtHead.getRight());
}
@Test
public void rootAndOneChild() {
head = new BST(1);
head.left = new BST(2);
serialized = "1,2,X,";
builtSerialized = BSTUtils.serializeBST(head);
assertEquals("root with left child", serialized, builtSerialized);
builtHead = BSTUtils.deserializeBST(builtSerialized);
assertEquals("only root tree rebuilt same value", head.getVal(), builtHead.getVal());
assertNotNull("only root tree rebuilt has left child", builtHead.getLeft());
assertEquals("only root tree rebuilt left child same value", head.left.getVal(), builtHead.left.getVal());
assertNull("only root tree rebuilt no right child", builtHead.getRight());
head = new BST(1);
head.right = new BST(2);
serialized = "1,X,2,";
builtSerialized = BSTUtils.serializeBST(head);
assertEquals("root with right child", serialized, builtSerialized);
builtHead = BSTUtils.deserializeBST(builtSerialized);
assertEquals("only root tree rebuilt same value", head.getVal(), builtHead.getVal());
assertNull("only root tree rebuilt no left child", builtHead.getLeft());
assertNotNull("only root tree rebuilt has right child", builtHead.getRight());
assertEquals("only root tree rebuilt right child same value", head.right.getVal(), builtHead.right.getVal());
}
@Test
public void rootAndTwoChildren() {
head = new BST(1);
head.left = new BST(2);
head.right = new BST(3);
serialized = "1,2,3,";
builtSerialized = BSTUtils.serializeBST(head);
assertEquals("root with both children", serialized, builtSerialized);
builtHead = BSTUtils.deserializeBST(builtSerialized);
assertTrue("rebuilt tree is same as original", BSTUtils.areEqualBST(head, builtHead));
}
/*
X means null
1
2 3
4 X 5 X
XX XX 6 7 XX
*/
@Test
public void sampleBST() {
head = new BST(1);
head.left = new BST(2);
head.right = new BST(3);
head.left.left = new BST(4);
head.right.left = new BST(5);
head.right.left.left = new BST(6);
head.right.left.right = new BST(7);
serialized = "1,2,3,4,X,5,X,X,X,X,X,6,7,X,X,";
builtSerialized = BSTUtils.serializeBST(head);
assertEquals("sample tree", serialized, builtSerialized);
builtHead = BSTUtils.deserializeBST(builtSerialized);
assertTrue("rebuilt tree is same as original", BSTUtils.areEqualBST(head, builtHead));
}
}
@steghio
Copy link
Author

steghio commented Mar 5, 2017 •
edited

Full description at:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment