Vertical Level order traversal of Binary Tree. | Java solution

Dear Friends,

I am with you with a data structure and algorithmic problem based on Binary tree and Hashing.

Given a binary tree we need to print the nodes according to vertical level ordering.



For above Binary tree the vertical level ordering is as below
4
2
1 5 6
3 8
7
9

Lets try to analyze the above binary tree  

1. Lets record the horizontal (left, right) distance of each node from root
2. To record horizontal distance for a node from root , lets see as how many lefts and how many rights do we need to travel from root's horizontal position to reach the node's horizontal position.
3. Lets take 1 Left step as -1 and 1 Right step as +1.

Node	Horizontal distance of Node from Root
Node with value 1 (root)	0	Root => 0
Node with value 2	-1	0 + (-1) = -1
Node with value 4	-2	-1+(-1) = -2
Node with value 5	0	-1 + 1= 0
Node with value 3	+1	0 + 1 = +1
Node with value 6	0	+1 +(-1) = 0
Node with value 8	+1	0 +1 = +1
Node with value 7	+2	+1 +1 = +2
Node with value 9	+3	2+1 = +3

With above analysis lets see the code in java for the solution of this problem.

package krishnalearnings.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class VerticalLevelOrderTraversal {
    public static class Node {
        private Node left;
        private Node right;
        private int data;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        // lets construct a tree
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node3 = new Node(3);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node6.right = node8;
        node7.right = node9;
        // tree constructed
        printVerticalLevelOrder(root);
    }

    private static void printVerticalLevelOrder(Node root) {
        TreeMap<Integer, List<Node>> map = new TreeMap<>();
        initilizeMap(root, 0, map);
        Set<Integer> horizontalDistances = map.keySet();
        for (Integer distance : horizontalDistances) {
            for (Node node : map.get(distance)) {
                System.out.print(node.data + " ");
            }
            System.out.println();
        }
    }

    private static void initilizeMap(Node root, int horizontalDistance, Map<Integer, List<Node>> map) {
        if (root != null) {
            List<Node> list = map.get(horizontalDistance);
            if (list == null) {
                list = new ArrayList<>();
                map.put(horizontalDistance, list);
            }
            list.add(root);
            initilizeMap(root.left, horizontalDistance - 1, map);
            initilizeMap(root.right, horizontalDistance + 1, map);
        }
    }
}

Largest sub array with sum equal to zero | Solution in Java

Hello Friends,

I am here with another famous algorithmic problem.

Given an Array of Integers, find the length of largest sub array such that the sum of the elements of the sub array is equal to zero. 

Points to ponder reading the problem statement.

1. Array can contain negative elements, positive elements, zero.
2. Array with all elements greater than zero will have zero sized Sub-Array. 
3. With two loops it can be solved with below. Its Time complexity is O(n²). It can be optimized to O(n) but lets first see the solution which comes simple to the mind.

 SOLUTION 1 with Time complexity is O(n²)

public class ZeroSubArrayMaxLength {
    public static void main(String[] args) {
        int[] array = {-12,3,1,-2,-1,1,10,0};
        int result = maxLength(array);
        System.out.println(result);
    }
    public static int maxLength(int[] array) {
        int N = array.length;
        int sum = 0, localLen = 0;
        int maxLen = 0;
        for (int i = 0; i < N; i++) {
            sum = array[i];
            localLen = 1;
            if (sum == 0 && maxLen == 0) {
                maxLen = 1;
            }
            for (int j = i + 1; j < N; j++) {
                sum = sum + array[j];
                localLen++;
                if (sum == 0 && localLen > maxLen) {
                    maxLen = localLen;
                }
            }
        }
        return maxLen;
    }
}

 

Now lets try to design the optimized solution with time complexity of O(n).

Suppose there is a person who starts a business with zero savings and he records the total savings accumulated in his account each day. 

On day 1 he records S1, on day 2 he records S2.

On day 5 he losses the amount equal to sum of what he earned on day 3 and day 4. 

Quick Question!! What is the total savings he records on day 5 ?

Answer : S2 (As day 3, day 4 and day 5 were actually resulted in 0 profit 0 loss.)

Extending this idea, lets see below image:

Extending the idea further lets see below Approach:

 

[ Note as how the entry in Hash Map is only put when we encounter a new sum, for the sum already present ( as key in Hash Map ) only the length of the sub array is computed and max length is updated if the length of the sub array is greater ]. 
 
Now Lets write the code finally!!

import java.util.HashMap;

public class ZeroSubArrayMaxLength {
    public static void main(String[] args) {
        int[] array = { 7, -5, -2, -3, 2, 1, 10 };
        int result = maxLength(array);
        System.out.println(result);
    }

    public static int maxLength(int A[]) {
        int n = A.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int sum = 0;
        int maxLength = 0;
        hashMap.put(0, -1); // initialization
        for (int i = 0; i < n; i++) {
            sum = sum + A[i];
            Integer pSumIndex = hashMap.get(sum);
            if (pSumIndex != null) {
                int localLength = i - pSumIndex;
                if (maxLength < localLength) {
                    maxLength = localLength;
                }
            } else {
                hashMap.put(sum, i);
            }
        }
        return maxLength;
    }
}