Longest consecutive sequence in Binary tree

Problem

Given a binary tree, we need to find length of the longest consecutive sequence path where path refers to sequence of node in tree along with parent child connection.

Solutions

We can solve this in two parts, one will find out the root to leaf path and second will check the longest sequence in that path. Root to leaf can be found by traversing tree using pre-order traversal. This way we can find out the longest sequence in binary tree. 

Solution below implements the approach.

import java.util.ArrayList;
import java.util.List;

public class LongestSeqInBT {
    private  List rootToLeafPath;
    private List longestSeq;

    public LongestSeqInBT(){
        rootToLeafPath = new ArrayList<>();
        longestSeq     = new ArrayList<>();
    }

    public void longestSeqInBTree(Node bTreeRoot, int index){
        if (bTreeRoot != null){
            if(rootToLeafPath.size() > index){
                rootToLeafPath.set(index, bTreeRoot.data);
            }
            else
                rootToLeafPath.add(bTreeRoot.data);

            longestSeqInBTree(bTreeRoot.left, index + 1);
            longestSeqInBTree(bTreeRoot.right, index + 1);
        }
        else {
            LongestSeqInList(index);
        }
    }

    private void LongestSeqInList(int index) {

        if (index <= 0)
            return;

        Integer prev = Integer.MAX_VALUE;
        Integer maxSeqSize = 1;
        Integer currentSeqSize = 1;
        Integer startIndex = -1;
        Integer counter = 0;
        for (Integer i : rootToLeafPath){
            counter++;
            if (i - 1 == prev){
                currentSeqSize++;
                if (currentSeqSize > maxSeqSize){
                    maxSeqSize = currentSeqSize;
                    startIndex = counter - currentSeqSize;
                }
            }
            else
                currentSeqSize = 1;
            prev = i;
        }

        if (maxSeqSize > longestSeq.size() && startIndex > -1){
            longestSeq.clear();
            for (int i = startIndex; i < startIndex + maxSeqSize ; i++) {
                longestSeq.add(rootToLeafPath.get(i));
            }
        }
    }
 
    public static void main(String[] args) {

        LongestSeqInBT btSeq = new LongestSeqInBT();

        Node node3 = new Node(3);
        Node node2 = new Node(2, node3, null);

        Node node7 = new Node(7);
        Node node6 = new Node(6, node7, null);
        Node node5 = new Node(5);
        Node node4 = new Node(4, node5, node6);

        Node bTree = new Node(1, node4, node2);

        Node.PrintInOrder(bTree);

        System.out.println("");
        btSeq.longestSeqInBTree(bTree, 0);
        for (Integer i : btSeq.longestSeq){
            System.out.print(i + " ");
        }
    } 
}

Comments are welcome. Question source geeksforgeeks

Rearrange array such that all odd numbers occupy odd positions

Problem:
Rearrange array such that all odd numbers occupy odd positions and even numbers occupy even position. Order of numbers needs to be maintained without use of extra space.

Solution:
For maintaining the number order, you can apply movement. if odd or even is not in place then find next required number and move other numbers to right. Solution below implements this.

 
public class OddEven {

    public static void main(String[] args) {

        int[] input = {1, 23, 4, 6, 2 , 3, 7, 12, 15, 16, 19, 100};

        System.out.println("Before : ");
        for (int i : input){
            System.out.print(i + " ");
        }

        oddEvenWithoutBuffer(input);

        System.out.println("\nAfter : ");
        for (int i : input){
            System.out.print(i + " ");
        }
    }

    static void oddEvenWithoutBuffer(int[] input) {

        for (int i = 0; i < input.length; i++) {

            int j = i + 1;
            if (i % 2 == 0) {
                if (input[i] % 2 != 0) {
                    while (j < input.length && input[j] % 2 != 0)
                        j++;
                } else continue;
            } else {
                if (input[i] % 2 == 0) {
                    while (j < input.length && input[j] % 2 == 0)
                        j++;
                } else continue;
            }

            if (j < input.length) {
                int temp = input[j];
                for (int m = j; m > i; m--) input[m] = input[m - 1];
                input[i] = temp;
                i++;    //Skip next as its in place, due to movement
            } else
                break;      //No more even or odd remaining.
        }
    }
}

Comments are welcome. Question source geeksforgeeks

Maximum sum such that no two elements are adjacent

Problem

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Solution

Simplest solution is to sum all the elements in the array, which are not adjacent and find out max sum. But this solution is not efficient. 

We can device this problem in smaller problem, like if we find out for a sub set of array the max sum once we can re-use this sum. 

Solution below implements both the approaches, one with all permutations and second using dynamic programing.

  
public class MaxSumWithoutAdjecent {
    private int[] dp;

    public MaxSumWithoutAdjecent(int size){
        setInputSize(size);
    }

    public void setInputSize(int size){
        dp = new int[size +1];
        for (int i=0; i < dp.length; i++)
            dp[i] = -1;
    }

    public int maxSumByDp(int[] array, int index){
        if (index >= array.length)
            return 0;
        if (dp[index] != -1)
            return dp[index];

        int max = Math.max( array[index] + maxSum(array, index + 2), maxSum(array, index + 1));
        dp[index] = max;
        return max;
    }

    public static void main(String[] args) {
        int[] array = {5,  5, 10, 40, 50, 35};

        MaxSumWithoutAdjecent maxsummer = new MaxSumWithoutAdjecent(array.length);

        System.out.println(maxSum(array, 0));
        System.out.println(maxsummer.maxSumByDp(array, 0));

        int[] array1 = {3, 2, 5, 10, 7};
        maxsummer.setInputSize(array1.length);
        System.out.println(maxSum(array1, 0));
        System.out.println(maxsummer.maxSumByDp(array1, 0));
    }

    public static int maxSum(int[] array, int index){
        if (index >= array.length)
            return 0;
        return Math.max( array[index] + maxSum(array, index + 2), maxSum(array, index + 1));
    }
}

Comments are welcome. Question source geeksforgeeks