I took a look at the “Is This a Binary Search Tree?” challenge at HackerRank. If interested in learning about this challenge and associated requirements use the following URL: https://www.hackerrank.com/challenges/ctci-is-binary-search-tree

The idea is quite simple. A BST should have all nodes in an ascending order when traversed using an in order traversal algorithm. If they do not, a value in a node is out of order rendering the tree as an invalid BST.

The challenge has an illustration of a correct BST. I went ahead and wrote some test code to populate a binary search tree with the sample data. Following is a screen capture of the Eclipse IDE when running on the binary tree used as an example:

main <<< inOrder: 1 2 3 4 5 6 7 main <<< checkBST: true

My test code written in Java follows:

/** * Insert node. */ static Node insert(Node root, int data) { // **** empty tree **** if (root == null) { // ???? alter the data for the BST ???? // if (data == 6) { // data = 1; // } // **** insert the data into the tree **** Node node = new Node(data); return node; } // **** insert on left side **** if (data <= root.data) { root.left = insert(root.left, data); } // **** insert on right side **** else { root.right = insert(root.right, data); } // **** **** return root; } /** * */ static void inOrder(Node root) { // **** **** if (root == null) { return; } if (root.left != null) { inOrder(root.left); } System.out.print(root.data + " "); if (root.right != null) { inOrder(root.right); } } /** * */ public static void main(String[] args) { Node root = null; // **** build tree **** root = insert(root, 4); root = insert(root, 2); root = insert(root, 6); root = insert(root, 1); root = insert(root, 3); root = insert(root, 5); root = insert(root, 7); // **** traverse tree **** System.out.print("main <<< inOrder: "); inOrder(root); System.out.println(); // **** check if BST **** System.out.println("main <<< checkBST: " + checkBST(root)); }

If the commented code in the **insert()** method is enabled, the program outputs the following:

main <<< inOrder: 1 2 3 4 1 5 7 main <<< checkBST: false

I used the program with different values to test it.

My solution in Java follows:

/** * Check if the data in the tree is in order. */ static boolean checkBST(Node root) { LinkedList<Integer> list = new LinkedList<Integer>(); // **** build list with node data **** saveData(root, list); // **** check if data is out of order **** for (int i = 1; i < list.size(); i++) { if (list.get(i - 1) >= list.get(i)) { return false; } } // **** data is in order **** return true; } /** * Traverse tree in order saving data to a list. */ static void saveData(Node root, LinkedList<Integer>list) { // **** **** if (root == null) { return; } if (root.left != null) { saveData(root.left, list); } list.add(root.data); if (root.right != null) { saveData(root.right, list); } }

The **checkBST()** method instantiates a FIFO list of integers. The **saveData()** method is a copy with modifications of the **inOrder()** method. It inserts the value of the node into the list. After the traversal is completed, the **checkBST()** method traverses the list looking for values not in ascending order. If consecutive elements are found out of order, the method returns false; otherwise it returns true.

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. I will reply as soon as possible and will not make use of your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter: **@john_canessa**