Create a gist now

Instantly share code, notes, and snippets.

@steghio /BST.java
Last active Apr 9, 2017

What would you like to do?
BST - binary search tree and binary trees
package com.blogspot.groglogs.bst;
import java.util.ArrayList;
import java.util.List;
public class BST {
//fields
int val;
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;
}
//with parent pointer
public BST(int val, BST parent){
this.val = val;
this.parent = parent;
}
//getters
public int getVal(){
return this.val;
}
//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;
}
//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<Integer>();
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 reach the end of a path?
if(i == path1.size()-1 || i == path2.size()-1){
distance = Math.abs(path1.size() - path2.size());
break;
}
//did we find the divergence point?
if(path1.get(i) != path2.get(i) || i == path1.size()-1 || i == path2.size()-1){
distance = path1.size() - i + path2.size() - i;
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;
}
}
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 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;
@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 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");
}
//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");
}
}
//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();
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("All right tree with parent is:");
tree.printTreeWParent();
}
@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();
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("All left tree with parent is:");
tree.printTreeWParent();
}
@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();
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("Random tree with parent is:");
tree.printTreeWParent();
}
@Test
//duplicate tree
public void duplicateTree() {
input = new int[]{13, 13, 13};
tree = BST.buildUnbalanced(input);
System.out.println("Duplicate tree is:");
tree.printTree();
//with parent
tree = BST.buildUnbalancedWParent(input);
System.out.println("Duplicate tree with parent is:");
tree.printTreeWParent();
}
//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));
}
//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));
}
@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 4: yes", 4, tree.find(4).getVal());
assertEquals("Find node 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 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);
}
@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));
}
@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());
}
@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));
}
@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));
}
@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);
}
@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);
}
@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);
}
@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);
}
@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("bfs 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("bfs 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("bfs visit 13, 2, 33, 1, 6, 18, 4, 20", 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));
}
@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));
}
@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.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;
}
}
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;
}
}