CTCI Challange, DAY 7

Day 7:-
I missed 1 day as i was busy in other stuff.

Problen Statement:- Is This a Binary Search Tree?

My approach:-

• First i solved BinaryTree logic completely.
• then i started with inorder traversal to check for BST correctness with left less than root and right greater than root.
• Used set to check for duplicates.

On Paper:-

package vikram.CTCI;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

/**
 * @author vikram.shanbogar@gmail.com
 * on 7/31/2017.
 */
public class BinaryTree {

    //  The Node class is defined as follows:
    static class Node {
        int data;
        Node left;
        Node right;

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

    List<Integer> list = new ArrayList<>();
    int counts = 1;
    Node root;
    boolean isBST = true;

    private boolean inorder(Node root) {

        if (root.left != null) {
            if (root.left.data >= root.data) {
                isBST = false;
            }
            counts++;
            inorder(root.left);
        }
        if (list.size() > 0 && root.data <= list.get(list.size() - 1)) {
            isBST = false;
        }
        list.add(root.data);
        //System.out.print(root.data + " ");
        if (root.right != null) {
            if (root.right.data <= root.data) {
                isBST = false;
            }
            counts++;
            inorder(root.right);
        }
        return isBST;
    }

    public void inorder() {
        inorder(root);
    }

    public void insert(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        } else
            insert(root, data);
    }

    public void insert(Node root, int data) {
        if (data < root.data) {
            if (root.left == null) {
                root.left = new Node(data);
                return;
            } else
                insert(root.left, data);
        }
        if (data > root.data) {
            if (root.right == null) {
                root.right = new Node(data);
                return;
            } else
                insert(root.right, data);
        }
    }

    public boolean checkBST(Node root) {
        inorder(root);
        if (new LinkedHashSet<>(list).size() < counts) {
            isBST = false;
        }
        System.out.println(isBST);
        return false;
    }
}

Improvements:-
Took more time than i thought.

Learnings:-
I learned more about inner classes,junit which was pending for a long time.