Is this a Binary Search Tree

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