[Java] Reverse doubly linked list

Here is a O(N) time and O(1) space method to reverse a doubly linked list:

 //reverse doubly linked list  
   public static DoubleLinkedListNode reverseList(DoubleLinkedListNode head){  
     if(head == null) return head;  
   
     DoubleLinkedListNode prev = null;  
   
     while(head != null){  
       DoubleLinkedListNode next = head.next;  
       head.next = prev;  
       prev = head;  
       head = next;  
     }  
   
     return prev;  
   }  

You can check the implementation on my Gist along with the definition of the DoubleLinkedList class and some test cases.

[Java] Find if binary tree is complete

A binary tree is complete if for each level, there are no holes between two children. For example:

complete =
        A
      B  C
there are no holes between B and C

complete =
        A
       B
there are no holes after B

non complete =
       A
        C
there is a hole before C

You can the code on my Gist (isTreeComplete) along with some test cases:

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

[Java] Find if a binary tree is balanced

A binary tree is balanced if the left and right branches do not differ in depth for more than one level.

Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:

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

I use an additional data structure (Entry) to pass around two pieces of information:

- is the tree balanced so far
- what is the current depth of the path being analyzed

[Java] Find depth of binary tree

Here is a simple method to find the depth of a given binary tree, no matter if it's balanced or not.

The null tree has depth -1, the root has depth 0 and so on. By looking at the depth it is immediately possible to get the max number of elements at that depth: 2^depth.

You can check the code on my Gist (getTreeDepth) along with some test cases:

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

[Java] LinkedList sum

Here's a simple exercise: given two positive numbers represented as linked lists, return their sum as a new linked list.

This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:

A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1

You can check the code and some tests on my Gist (LinkedListSumJTests):

 /*  
   Given two lists representing integer numbers  
   with the least significant digit in the head position  
   return a new list containing the sum  
   */  
   public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){  
     if(x == null && y == null) return null;  
   
     int carry = 0, curr = 0, val = 0;  
     SingleLinkedListNode result = null, n = null;  
   
     //keep going until we have data in either list and do not forget the last carry!  
     while(x != null || y != null || carry != 0){  
       curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry  
       val = curr % 10; //take only LSD  
   
       //track if we have a carry  
       carry = (curr >= 10) ? 1 : 0;  
   
       if(n == null){  
         n = new SingleLinkedListNode(val);  
         result = n;  
       }  
       else{  
         n.next = new SingleLinkedListNode(val);  
         n = n.next;  
       }  
   
       //move to next digit  
       if(x != null) x = x.next;  
       if(y != null) y = y.next;  
   
     }  
   
     return result;  
   }  

[Java] Rolling average for both sorted and unsorted streams

The rolling, moving, running, whatever movement verb you like median or average is a problem regarding the online calculation of the average element in a streaming dataset.

The pro version requires you to sort the data on the fly in order to produce the median result:

input = 9, 4, 10, 3, 3
output = 4 because sorted input is: 3, 3, 4, 9, 10

The base version just wants the actual median element of the stream:

input = 9, 4, 10, 3, 3
output = 10

If the stream length is odd, the median is the actual median element, otherwise it's the average of the two elements near the middle of the stream.

The solution to both returns the median in constant O(1) time and keeps it updated in O(N) time. Also they both use additional O(N) space.

[Java] Reconstruct binary tree from visits

An alternative way to represent a binary tree is to use an array. If the tree is a binary search tree and is also perfectly balanced, it's easy to find each node with the formula:

node         = idx of node in array
left child   = 2 * idx of node in array + 1
right child = 2 * idx of node in array + 2

But if the tree is not balanced, we need more information. For example, given a inorder and a postorder visit of the tree, we can rebuild it easily.

The idea is as such:

• in the preorder visit array at position 0 we have the root
• in the inorder visit array 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, without considering the content.

[Java] Binary Tree visits

Given a binary tree, we have many ways of visiting it, depending on our goals:

• BFS: search tree by levels
• DFS inorder: visit root first, then left, then right
• DFS preorder: visit left, then root, then right. Useful to retrieve the tree values in ascending order
• DFS postorder: visit left, then right, then root. Useful when deleting the tree

You can check the code on my Gist.

BFS:

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

DFS - inorder:

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

DFS - preorder:

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

DFS - postorder:

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

The code works with Java 8 because converting a List to an array[] is now super simple thanks to the black magic behind list.stream().mapToInt(i -> i).toArray()