Create a gist now

Instantly share code, notes, and snippets.

@steghio /AAA_BST.txt
Last active Dec 10, 2017

What would you like to do?
BST - binary search tree and binary trees
Placeholder for naming
package com.blogspot.groglogs.bst;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BST {
//fields
int val, lockedChilds, height; //balance +1 = right heavy, 0 = balanced, -1 = left heavy
boolean isLocked;
public BST left, right, parent; //parent is only used if we build and handle a tree with parent pointers using the specific methods <name>WParent
//constructors
public BST(int val){
this.val = val;
this.isLocked = false;
this.lockedChilds = 0;
this.height = 1;
}
//with parent pointer
public BST(int val, BST parent){
this.val = val;
this.isLocked = false;
this.parent = parent;
this.lockedChilds = 0;
this.height = 1;
}
//getters
public int getVal(){
return this.val;
}
public int getLockedChilds(){
return this.lockedChilds;
}
public int getBalance(){
return ((this.right != null) ? this.right.height : 0) - ((this.left != null) ? this.left.height : 0);
}
//setters
public void setLeft(BST left){
this.left = left;
}
public void setRight(BST right){
this.right = right;
}
//helper for buildUnbalanced
private void addNode(int val){
if(val <= this.val){
if(this.left == null) this.left = new BST(val);
else this.left.addNode(val);
}
else{
if(this.right == null) this.right = new BST(val);
else this.right.addNode(val);
}
}
public static BST buildUnbalanced(int[] input){
if(input == null || input.length == 0)return null;
//create root then build tree recursively
BST tree = new BST(input[0]);
for(int i = 1; i < input.length; i++){
tree.addNode(input[i]);
}
return tree;
}
//helper for buildUnbalancedParent
private void addNodeWParent(int val, BST parent){
if(val <= this.val){
if(this.left == null) this.left = new BST(val, parent);
else this.left.addNodeWParent(val, this.left);
}
else{
if(this.right == null) this.right = new BST(val, parent);
else this.right.addNodeWParent(val, this.right);
}
}
//build unbalanced tree and keep parent pointers for each node
public static BST buildUnbalancedWParent(int[] input){
if(input == null || input.length == 0)return null;
//create root then build tree recursively
BST tree = new BST(input[0]);
for(int i = 1; i < input.length; i++){
tree.addNodeWParent(input[i], tree);
}
return tree;
}
//helper for balanceAVL. Given a node returns the current height. That is the max between left and right heights + 1
public int getHeight(){
return Math.max(((this.left != null) ? this.left.height : 0), ((this.right != null) ? this.right.height : 0)) + 1;
}
//helper for balanceAVL. Node is the unbalanced one (-2 or +2 factor). In the examples is the root
//This is because A is left heavy (-2 balance) and B has no right child (-1 balance) so they both lean the same side
/*
Right rotate B->A example:
A
B
C
Returns:
B
C A
*/
private BST rightRotate(BST node){
//save current parent node and new subroot node (current.left)
BST parent = node.parent;
BST subroot = node.left;
//are we right or left child, our parent has to point to the new subroot correctly
if(parent != null){
if(parent.left == node) parent.left = subroot;
else parent.right = subroot;
}
//move right child of new subroot as left child of current subroot
node.left = subroot.right;
if(subroot.right != null){
subroot.right.parent = node;
}
//set current node as right child of new subroot
subroot.right = node;
node.parent = subroot;
//set the new subroot parent
subroot.parent = parent;
//update heights. Update first the previous subroot height (current right child), then the new subroot height!
node.height = node.getHeight();
subroot.height = subroot.getHeight();
return subroot;
}
//This is because A is right heavy (+2 balance) and B has no left child (+1 balance) so they both lean the same side
/*
Left rotate A<-B example:
A
B
C
Returns:
B
A C
*/
private BST leftRotate(BST node){
//save current parent node and new subroot node (current.right)
BST parent = node.parent;
BST subroot = node.right;
//are we right or left child, our parent has to point to the new subroot correctly
if(parent != null){
if(parent.left == node) parent.left = subroot;
else parent.right = subroot;
}
//move left child of new subroot as right child of current subroot
node.right = subroot.left;
if(subroot.left != null){
subroot.left.parent = node;
}
//set current node as left child of new subroot
subroot.left = node;
node.parent = subroot;
//set the new subroot parent
subroot.parent = parent;
//update heights. Update first the previous subroot height (current right child), then the new subroot height!
node.height = node.getHeight();
subroot.height = subroot.getHeight();
return subroot;
}
//first right rotate node.right.left, then left rotate node.right
//This is because A is right heavy (+2 balance) and B has a left child (-1 balance) so they lean opposite sides
/*
rightLeft rotate C->B-A example:
A
B
C
Step 1 right rotate C->B:
A
C
B
Step 2 left rotate C->A returns:
C
A B
*/
private BST rightLeftRotate(BST node){
BST subroot = rightRotate(node.right);
subroot = leftRotate(subroot.parent);
return subroot;
}
//first left rotate node.left.right, then right rotate node.left
//This is because A is left heavy (-2 balance) and B has a right child (+1 balance) so they lean opposite sides
/*
leftRight rotate C->B-A example:
A
B
C
Step 1 left rotate C->B:
A
C
B
Step 2 right rotate C->A returns:
C
B A
*/
private BST leftRightRotate(BST node){
BST subroot = leftRotate(node.left);
subroot = rightRotate(subroot.parent);
return subroot;
}
//helper for addNodeAVL
private BST balanceAVL(BST node){
//walk all the way up to the root while checking the balance factors and if needed perform adjusting rotations
//the rotations already adjust the balance as well
BST root = node;
while(node != null){
//right rotation needed
if(node.getBalance() == -2){
//check left child balance to verify if we need double rotation
//single rotation, both lean the same side
if(node.left.getBalance() != 1) node = rightRotate(node);
//double rotation, child leans opposite side
else node = leftRightRotate(node);
}
//left rotation needed
if(node.getBalance() == 2){
//check right child balance to verify if we need double rotation
//single rotation, both lean the same side
if(node.right.getBalance() != -1) node = leftRotate(node);
//double rotation, child leans opposite side
else node = rightLeftRotate(node);
}
root = node;
node = node.parent;
}
return root;
}
//helper for buildBalancedAVL
private BST addNodeAVL(int val, BST parent){
//duplicates are not allowed
if(val == this.val) return this;
//insert node normally and adjust balance later
if(val < this.val){
if(this.left == null) this.left = new BST(val, parent);
else this.left.addNodeAVL(val, this.left);
}
else{
if(this.right == null) this.right = new BST(val, parent);
else this.right.addNodeAVL(val, this.right);
}
//adjust node height
this.height = this.getHeight();
//no need to propagate height change back to root, the balance function will update the heights while retracing to the root
//check tree is still balanced
return balanceAVL(this); //this is the node where we inserted the child, we return the new tree root
}
//build balanced AVL tree. All nodes have parent pointer
public static BST buildBalancedAVL(int[] input){
if(input == null || input.length == 0)return null;
//create first then build tree recursively
BST root = new BST(input[0]);
for(int i = 1; i < input.length; i++){
root = root.addNodeAVL(input[i], root);
}
return root;
}
//utilities
public void printTree(){
System.out.println("Val: " + this.val);
if(this.left != null)this.left.printTree();
if(this.right != null)this.right.printTree();
}
public void printTreeWParent(){
if(this.parent != null) System.out.println("Val: " + this.val + " - Parent: " + this.parent.val);
else System.out.println("Val: " + this.val + " - Parent: NULL");
if(this.left != null)this.left.printTreeWParent();
if(this.right != null)this.right.printTreeWParent();
}
public boolean contains(int val){
if(val == this.val)return true;
else if(val <= this.val)return this.left == null ? false : this.left.contains(val);
else return this.right == null ? false : this.right.contains(val);
}
//return a node that contains val. In case of duplicate nodes, return the first one we encounter
public BST find(int val){
if(val == this.val)return this;
else if(val <= this.val)return this.left == null ? null : this.left.find(val);
else return this.right == null ? null : this.right.find(val);
}
//are two nodes equals
public boolean isEqualNode(BST otherNode){
if(otherNode != null) return this.val == otherNode.val;
return false;
}
//helper for findPath
private void addPath(List<Integer> path, int val){
//always add current element to the path
path.add(this.val);
//stop if we are the element we were looking for or there is no more place to move to
if(val == this.val) return;
else if(val <= this.val){
if(this.left != null)this.left.addPath(path, val);
}
else{
if(this.right != null)this.right.addPath(path, val);
}
}
//returns the DFS path to the specified value if it exists
public List<Integer> findPath(int val){
if(!this.contains(val)) return null;
ArrayList<Integer> path = new ArrayList<>();
this.addPath(path, val);
return path;
}
/*
using path lists, finds the distance between two elements in the tree
0 if same element
-1 if at least one element is not in the tree
*/
public int distance(int val1, int val2){
if(!this.contains(val1) || !this.contains(val2)) return -1;
int distance = 0;
//we know the element is in the tree because we checked earlier
if(val1 == val2)return distance;
//find paths to both elements, we know they must be there and are not the same by now
List<Integer> path1, path2;
path1 = this.findPath(val1);
path2 = this.findPath(val2);
/*
search the path lists until the divergence point
the distance is the sum of the remaining distances from the divergence point to the end of both paths
or if we reached the end of one of the lists, it's simply the difference in path sizes
*/
for(int i = 0; i < Math.min(path1.size(), path2.size()); i++){
//did we find the divergence point?
if(path1.get(i) != path2.get(i)){
distance = path1.size() - i + path2.size() - i;
break;
}
//did we reach the end of a path?
if(i == path1.size() - 1 || i == path2.size() - 1){
distance = Math.abs(path1.size() - path2.size());
break;
}
}
return distance;
}
//helper for findLCA
private BST LCA(int val1, int val2){
//if I am the element, I am also the common ancestor because the other has to be my child or myself again
if(this.val == val1 || this.val == val2) return this;
//if both elements are on the left subtree, search there
if(val1 <= this.val && val2 <= this.val){
if(this.left != null) return this.left.LCA(val1, val2);
else return null;
}
//otherwise search on the right
if(val1 > this.val && val2 > this.val){
if(this.right != null) return this.right.LCA(val1, val2);
else return null;
}
//otherwise I am the branching element so I am the lowest common ancestor
return this;
}
//lowest common ancestor. MUST be used in conjunction with contains since we are not always sure that both elements are in the tree!
public BST findLCA(int val1, int val2){
BST lca = this.LCA(val1, val2);
//what if we found the potential branching point but the other element is not in the tree?
if(lca != null && (!lca.contains(val1) || !lca.contains(val2)))return null;
return lca;
}
//helper for findPathDistance
private int pathDistance(int val, int distance){
//found it
if(this.val == val) return distance;
//otherwise increase the distance and search in the proper subtree
distance++;
if(val <= this.val) return this.left.pathDistance(val, distance);
else return this.right.pathDistance(val, distance);
}
//find the distance from one element to another. Wanting to use recursion we use an external variable to be updated while navigating
public int findPathDistance(int val){
int distance = 0;
return this.pathDistance(val, distance);
}
/*
using lowest common ancestor, finds the distance between two elements in the tree
0 if same element
-1 if at least one element is not in the tree
*/
public int distanceWLCA(int val1, int val2){
if(!this.contains(val1) || !this.contains(val2)) return -1;
int distance = 0;
//we know the element is in the tree because we checked earlier
if(val1 == val2)return distance;
//we know it won't be null because we checked already that both values are in the tree
BST lca = this.findLCA(val1, val2);
//distance is simply sum of paths from lca to both nodes
distance = lca.findPathDistance(val1) + lca.findPathDistance(val2);
return distance;
}
/*
using parent pointers, finds the distance between two elements in the tree
0 if same element
-1 if at least one element is not in the tree
*/
public int distanceWParent(int val1, int val2){
int path1 = 0, path2 = 0, dist1 = 0, dist2 = 0;
BST node1 = this, node2 = this;
//navigate to the first element and track the path length
while(node1 != null){
if(val1 == node1.val) break;
path1++;
if(val1 <= node1.val) node1 = node1.left;
else node1 = node1.right;
}
//if we did not find it, return -1, no need to keep checking, otherwise repeat the operation for the second element
if(node1 != null){
while(node2 != null){
if(val2 == node2.val) break;
path2++;
if(val2 <= node2.val) node2 = node2.left;
else node2 = node2.right;
}
}
else return -1;
/*
if we do not have the second element, return -1, no need to calculate distance
otherwise starting from the deepest node (longest path) navigate up to its parent and reduce the its total path distance
then check if both nodes are the same or share the same parent or we are at the root
as soon as we find a match, we are at the lowest common ancestor
and the total distance is the sum of the remaining paths from this point to the two nodes
*/
if(node2 != null){
dist1 = path1;
dist2 = path2;
//also works with simple node1 != node2
while(!node1.isEqualNode(node2)){
//to break ties, we just run this also if path1 = path2. Works the other way as well
if(path1 <= path2){
path2--;
if(node2 != null) node2 = node2.parent;
else break;//stop when we are the root
}
else{
path1--;
if(node1 != null) node1 = node1.parent;
else break;//stop when we are the root
}
}
}
else return -1;
return dist1 - path1 + dist2 - path2;
}
/*
Implement locking mechanism using a tree structure. A node can be locked if and only if no
descendant or ancestor is locked.
To keep the lock test operation O(1) and lock and unlock operations O(H) with H = height of the tree
we track the number of currently locked nodes in the node subtree so that we only need to walk up to the root
to test is a node can be locked and to update the extra info we track.
*/
public boolean isLocked(){
return this.isLocked;
}
//return true if we could lock successfully
public boolean lock(){
//if this node is locked or any of his descendants are, we cannot lock
if(this.isLocked() || this.lockedChilds > 0) return false;
//test if any ancestor is locked
BST curr = this.parent;
while(curr != null) {
if(curr.isLocked) return false;
curr = curr.parent;
}
//if we got here, we can safely lock this node
this.isLocked = true;
//and update the ancestor locked count
curr = this.parent;
while(curr != null) {
curr.lockedChilds++;
curr = curr.parent;
}
return true;
}
public void unlock(){
if(this.isLocked()) {
this.isLocked = false;
//update the ancestor locked count
BST curr = this.parent;
while (curr != null) {
curr.lockedChilds--;
curr = curr.parent;
}
}
}
//return the size of the (sub)tree (number of nodes)
public int size(){
int res = 0;
Queue<BST> q = new LinkedList<>();
q.add(this);
while(!q.isEmpty()){
res++;
BST t = q.remove();
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
return res;
}
}
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 static org.junit.Assert.*;
public class BSTJTests {
BST tree = null;
int[] input = null, preorder = null, inorder = null, postorder = null, output = null, bfs = null;
List<Integer> path = null;
int depth = 0;
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());
//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());
//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());
//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());
//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());
//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());
//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());
//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());
//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
//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));
}
}
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());
}
}
}
package com.blogspot.groglogs.bst;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BSTUtils {
/*
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();
}
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, HashMap<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 incuding 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;
}
}
package com.blogspot.groglogs.bst;
public class Entry {
public boolean isBalanced;
public int height;
public Entry(boolean isBalanced, int height){
this.isBalanced = isBalanced;
this.height = height;
}
}