Detecting if a binary tree is a Binary Seach Tree: Java implementation

Hello Friends,

Today I am with you with another algorithm. Its about detecting if a Binary tree is a BST or not. A regular binary tree is a tree for which each node has number of children equal to 0, 1 or 2. A binary search tree has same properties as of regular binary tree with an additional property according to which any node has data  smaller than the data in its right child and greater data than the data in its left child.


We have two binary trees below.







Friends Lets look at the Java implementation solving this problem statement.

[Note that tree[] holds actual tree node values, left[] holds the index in tree[] corresponding to the left child of the each index and right[] holds the index in tree[] corresponding to the right child of the each index]

public class BSTDetector {
    // tree holds actual tree node values
    Integer tree[];
    // holds the index in tree[] corresponding to the left child of the each index
    Integer left[];
    // holds the index in tree[] corresponding to the right child of the each index
    Integer right[];

    public boolean isBinaryTreeBST(Integer tree[], Integer left[], Integer right[]) {
        this.tree = tree;
        this.left = left;
        this.right = right;
        return detectBST(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
    }

    private boolean detectBST(int leftRange, int rightRange, int currentIndex) {
        boolean isLeftChildvalid = true;
        boolean isRightChildValid = true;
        if (left[currentIndex] != null) {
            isLeftChildvalid = tree[currentIndex] >= tree[left[currentIndex]];
        }
        if (right[currentIndex] != null) {
            isRightChildValid = tree[currentIndex] <= tree[right[currentIndex]];
        }
        boolean isInRange = leftRange <= tree[currentIndex] && tree[currentIndex] <= rightRange;
        if (!isRightChildValid || !isLeftChildvalid || !isInRange) {
            return false;
        }
        boolean isLeftTreeBST = true;
        boolean isRightTreeBST = true;
        if (left[currentIndex] != null) {
            isLeftTreeBST = detectBST(leftRange, tree[currentIndex], left[currentIndex]);
        }
        if (right[currentIndex] != null) {
            isRightTreeBST = detectBST(tree[currentIndex], rightRange, right[currentIndex]);
        }

        return isLeftTreeBST && isRightTreeBST;
    }

    public static void main(String[] args) {
        Integer tree[] = { 10, 8, 6, 22, 12, 14 };
        Integer left[] = { 1, null, null, null, null, 2 };
        Integer right[] = { 4, null, null, null, 5, 3 };
        BSTDetector bstDetector = new BSTDetector();
        boolean isBST = bstDetector.isBinaryTreeBST(tree, left, right);
        System.out.println(isBST);

        Integer anotherInputTree[] = { 10, 8, 14, 22, 12, 15 };
        Integer anotherInputLeft[] = { 1, null, null, null, null, 2 };
        Integer anotherInputRight[] = { 4, null, null, null, 5, 3 };
        isBST = bstDetector.isBinaryTreeBST(anotherInputTree, anotherInputLeft, anotherInputRight);
        System.out.println(isBST);
    }
}

 

Root to Leaf Sum in a Binary tree : java Implementation

Hello friends,

Suppose we have a binary tree (not necessary a binary search tree), whose each node represent an Integer. We have a number: SUM. We need to find if there exist a path from Root to any Leaf such that sum of all the nodes equals the SUM. The path should contain full path from Root to a Leaf node.



If we have a binary tree as above and SUM as 26 then the Valid path comprises of (11,5,10) and not 10 and 16 as 10 and 16 is not a complete path from root to leaf but (11,5,10) nodes create a path from root (10) to leaf (11).


Friends, please find below the java code solving this problem. Please note that for representing the binary tree three arrays have been used. :
1. tree[] : This holds the actual values of the tree. This is 0 indexed array.
2. left[] : This  holds index of left child for the current index.
3. right[] : This holds index of right child for the current index.

public class RootToLeafSumInBinaryTree {
    
    // tree holds actual tree node values
    static Integer tree[] = { 10, 16, 5, -3, 6, 11 };
    // holds the index in tree[] corresponding to the left child of the each index
    static Integer left[] = { 1, null, 4, null, null, null };
    // holds the index in tree[] corresponding to the right child of the each index
    static Integer right[] = { 2, 3, 5, null, null, null };
    static Integer result[] = new Integer[tree.length];
    static int resultIndex = 0;

    public static void main(String[] args) {

        Integer sum = 21;
        boolean isSuccess = rootToSum(0, sum);
        for (int i = 0; isSuccess &&  i < resultIndex; i++) {
            System.out.println(result[i]);
        }
    }

    public static boolean rootToSum(int currentIndex, Integer sum) {
        if (left[currentIndex] == null && right[currentIndex] == null) {
            if (sum - tree[currentIndex] == 0) {
                result[resultIndex++] = tree[currentIndex];
                return true;
            } else {
                return false;
            }
        }
        boolean isLeftSuccess = false;
        boolean isRightSuccess = false;
        sum = sum - tree[currentIndex];
        if (left[currentIndex] != null) {
            isLeftSuccess = rootToSum(left[currentIndex], sum);
        }
        if (right[currentIndex] != null) {
            isRightSuccess = rootToSum(right[currentIndex], sum);
        }
        // be careful here we need to see if we get success from Either of Left
        // or Right branch we need to return Success as we have a path where the
        // sum is equal to the provided sum. 
        if (isLeftSuccess || isRightSuccess) {
            result[resultIndex++] = tree[currentIndex];
            return true;
        }
        return false;
    }
}

 

Topologial sort : Java Implementation

Hello Friends,

I am here with you with another algorithm. Its Topological sorting of a directed graph. Suppose we have few tasks which are interdependent. Lets represent this system in a graph. Each task is represented by a Vertex and will be connected to the Vertices with which it has dependency relation. All Vertices connected to a Vertex V with INCOMING edges on V will be the vertices on  which  Vertex V is dependent upon. So all the tasks represented by the such vertices should be performed before task represented by Vertex V is completed.


A such system represented as graph is as below :





Here for example Before task represented by C is performed , Tasks represented by  A and B must be performed as C has dependency on A and B.

Friends Please find below the code for the same. I have used my own custom HashMap and Stack for its implementation, so you can see a basic internal working of HashMap and Stack also.

public class TopologicalSort {

    public static class Graph {
        int maxSize;
        int size;
        Vertex vertices[];
        HashMap map;
        Stack stack;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            vertices = new Vertex[maxSize];
            map = new HashMap();
            stack = new Stack(maxSize);
        }

        public static class Vertex {
            char name;
            Neighbour adj;
            State state = State.NEW;

            public Vertex(char name) {
                this.name = name;
            }
        }

        public enum State {
            NEW, INPROGRESS, VISITED
        }

        public static class Neighbour {
            Vertex vertex;
            Neighbour next;

            public Neighbour(Vertex vertex, Neighbour next) {
                this.vertex = vertex;
                this.next = next;
            }
        }

        public void invokeTopologicalSorting() {
            for (int i = 0; i < maxSize; i++) {
                exploreVertex(vertices[i]);
            }
            for (int i = 0; !stack.isEmpty(); i++) {
                System.out.println(stack.pop().name);
            }
        }

        /**
         * 
         * The basic idea in this method is to fully explore the vertex, and
         * check if its any Neighbor has been left un explored, if so then need
         * to explore the Neighbor by recursive call to this method. After fully
         * exploring we need to add the vertex to the stack. Thus first the
         * leaves will be pushed to the stack and then when the vertex is re
         * visited by recurrence stack then we see if there are any more
         * neighbor left un explored , if so we need to repeat the process else
         * we come out of the while loop and push the explored vertex in the
         * stack.
         * 
         * Point to note here is: A vertex if considered a Task has dependencies
         * on the vertices which are connected to it by In-coming edges. So for
         * any Vertex, V we need to explore its neighbor first so that they are
         * pushed to the stack first (and will be popped after the current
         * vertex, V).
         */
        public void exploreVertex(Vertex v) {
            if (v.state != State.VISITED) {
                v.state = State.VISITED;
                Neighbour adj = v.adj;
                while (adj != null) {
                    Vertex neighbour = adj.vertex;
                    if (neighbour.state != State.VISITED) {
                        exploreVertex(adj.vertex);
                    }
                    adj = adj.next;
                }
                stack.push(v);
            }
        }

        public void addVertex(char name) {
            vertices[size++] = new Vertex(name);
            map.put(name, vertices[size - 1]);
        }

        public void addNeighbour(char source, char destination) {
            Vertex sourceV = map.get(source);
            Vertex destinationV = map.get(destination);
            sourceV.adj = new Neighbour(destinationV, sourceV.adj);
        }

        public static class Stack {
            Vertex[] stack;
            int maxSize;
            int top = -1;

            public Stack(int maxSize) {
                this.maxSize = maxSize;
                stack = new Vertex[maxSize];
            }

            public void push(Vertex u) {
                stack[++top] = u;
            }

            public Vertex pop() {
                Vertex v = stack[top];
                stack[top] = null;
                top--;
                return v;
            }

            public boolean isEmpty() {
                return top == -1;
            }
        }

        public static class HashMap {
            int prime = 499;
            MapNode[] map = new MapNode[prime];

            public static class MapNode {
                char key;
                Vertex value;
                MapNode next;

                MapNode(char key, Vertex value, MapNode next) {
                    this.key = key;
                    this.value = value;
                    this.next = next;
                }
            }

            public int index(char key) {
                return hashcode(key) % prime;
            }

            public int hashcode(char key) {
                return 31 * key;
            }

            public boolean put(char key, Vertex value) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return false;
                    }
                    temp = temp.next;
                }
                map[index] = new MapNode(key, value, map[index]);
                return true;
            }

            public Vertex get(char key) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return temp.value;
                    }
                    temp = temp.next;
                }
                return null;
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');
        graph.addVertex('G');
        graph.addVertex('H');
        graph.addNeighbour('A', 'C');
        graph.addNeighbour('B', 'C');
        graph.addNeighbour('B', 'D');
        graph.addNeighbour('C', 'E');
        graph.addNeighbour('D', 'F');
        graph.addNeighbour('E', 'F');
        graph.addNeighbour('E', 'H');
        graph.addNeighbour('F', 'G');
        graph.invokeTopologicalSorting();
    }
}

 

Printing elements of a Binary Tree in Spiral Order Traversal using Java.

Hello Friends,

I am here again with yet another algorithm. Lets say we have a binary tree and we wish to traverse it in a special way.
Lets start traversal of the tree from left starting at the 0th level i.e. the root element. As we move to the next level i.e. level 1 then lets start the traversal from right so all the children of the root are traversed right to left. As we move to next level lets reverse the direction of traversal.






For example for the graph above the traversal should be like 1 2 3 4 6 5 7 8. At each level the traversal direction is changed and we start from root with left direction.

Friends, please have a look at the code below for the implementation of this type of traversal. I have used ArrayDeque to get the implementation of Stack ( java.util.Stack has all its methods synchronized and I do not need synchronization in my current implementation, hence I have used java.util.ArrayDeque). We can eaisly replace the ArrayDeque with our custom stack if we want, but for this example below lets proceed with ArrayDeque.

import java.util.ArrayDeque;

public class SpiralBinaryTreeTraversal {

    public static void main(String[] args) {
        int[] nodes = { 1, 2, 3, 4, 5, 6, 7, 8 };
        int left[] = { -1, 3, -1, -1, 7, -1, -1, -1 };
        int right[] = { 2, 4, 5, 6, 8, - 1, -1, -1 };
        printSpiral(nodes, left, right);
    }

    public static void printSpiral(int nodes[], int left[], int right[]) {
        ArrayDeque<Integer> leftStack = new ArrayDeque<>();
        ArrayDeque<Integer> rightStack = new ArrayDeque<>();
        leftStack.push(nodes[0]);
        boolean isLeft = true;
        int current, currentIndex;
        while(!leftStack.isEmpty() || !rightStack.isEmpty()){
            if(isLeft){
                current = leftStack.pop();
                currentIndex = current-1;
                if(left[currentIndex] != -1){
                    rightStack.push(left[currentIndex]);
                }
                if(right[currentIndex] != -1){
                    rightStack.push(right[currentIndex]);
                }
                System.out.println(current);
                if(leftStack.isEmpty()){
                    isLeft = !isLeft;
                }
            }else{
                current = rightStack.pop();
                currentIndex = current-1;
                if(right[currentIndex] != -1){
                    leftStack.push(right[currentIndex]);
                }
                if(left[currentIndex] != -1){
                    leftStack.push(left[currentIndex]);
                }
                System.out.println(current);
                if(rightStack.isEmpty()){
                    isLeft = !isLeft;
                }
            }
        }
    }
}