BST Search

It is a Saturday in August in the Twin Cities of Minneapolis and St. Paul and it is going to be a warm and humid day. My wife is out shopping with a friend and I am in my home office having fun with Binary Search Trees (BSTs).

This past week I was talking with a software engineer about coding interviews. I have mixed thoughts about them. Not sure about their value as far as finding out if a person is able to develop quality software. Allow me to describe the process which seems to be quite spread around the industry.

The candidate is interviewed by multiple technical people. The idea is to present the candidate with a set of one or more programming problems and expect working code written on a whiteboard. Typically the programming language of choice is up to the candidate.

Before going any further, I have been developing commercial software products from ideas to production (full SLC) for a few decades. During that time I have used different programming languages (i.e., C, C++, and C #, Java, among others). I have developed code in different platforms (i.e., Apple, embedded, Linux, and Windows, among others). Given that I owned a software development company I have millions of lines of production code that I generated. In all that time, I do not ever recall using a whiteboard to write code with the idea of replicating it using an IDE to verify it compiles and runs. To be honest with you, I have also worked for small, medium and large companies and have never run into a developer that uses such technique.

What I do is a diagram to architect and design software before a single line of code is produced. For that task I typically use Microsoft Visio and paste the drawings into Microsoft Word so I end up with some verbiage and a picture. Yes, I do believe that a picture is worth 1,000 words so I do not have to write too many when they are accompanied by an image.

One more thing I do when developing software. I use the Test Driven Development (TDD) process. In a nutshell you start with a documented idea (note previous paragraph) and start with a blank canvas in your favorite IDE. Depending on the programming language and platform, I tend to use Microsoft Visual Studio (several versions), Eclipse, and JetBrains among others. Armed with a design I start writing code and calling methods in classes until I get to a working piece of code. Depending on complexity, I might edit the diagram making changes or additions. It is an iterative approach.  To learn more about TDD you may wish to read here.

If you follow this blog I mention that the best approach to learn something is to experiment with it. When confronted with a food you have never tried before, you can abstain testing because you might not like it. When you hear about an idea, you may not like it because it goes against your believes so you do not learn about it. In general I like to experiment and determine if there is value to different ideas, procedures, and items. Then and only then I can formulate my own valid opinion.

Earlier this week I purchased from Amazon a 48 x 32 inch mobile whiteboard. It should be delivered next week. As I am writing this post, I just ordered a copy of “Cracking the Coding Interview” by Gayle Laakmann McDowell. I believe I have watched a couple of her videos since I started this blog. The software engineer I was talking with recommended her book which should help me understand coding on a whiteboard.

My plan is to address the interview questions from the book using the whiteboard. When done will reproduce my approach using an IDE. After a couple dozen questions I should have enough experience in the practice to provide my opinion in this blog.

Now let’s get to the main topic for this post. This week while browsing YouTube I noticed one that appeared to cover how to search a Binary Search Tree (BST) and determine if a specified value is present or not. Earlier I located the video “Searching an Item in BST” by Tutorials Point (India). I watch the first 30 seconds or so because I wanted to copy the exact tree being used. I will probably want the entire video after this post to see if some new concepts / ideas are covered.

Following is a diagram of the BST I generated using Microsoft Visio.

The BST has 9 nodes including the root. It is a BST because all nodes to the left of any node hold values less than the selected node and all nodes to the right have larger values. For example, n1 has a value of 27 so all nodes to its left have values less than 27 (13 and 26). The only value to its right has a value of 30 which is larger than 30. This holds true for all nodes in the BST.

The idea is to specify a value and search for it in the BST. We want to know if the specified value is found or not.

The testing scaffolding follows:

package canessa.tree.ops;

import java.util.Scanner;

/*
 * Test scaffolding. 
 */
public class Solution {
	
	/*
	 * This code includes several algorithms using binary trees.
	 */
	public static void main(String[] args) {

		// **** open scanner ****
		Scanner sc = new Scanner(System.in);
		
		// **** allocate nodes for the BST ****
		Node n1 = new Node(27);
		Node n2 = new Node(13);
		Node n3 = new Node(30);
		Node n4 = new Node(26);
		
		Node n5 = new Node(56);
		Node n6 = new Node(40);
		Node n7	= new Node(65);
		Node n8	= new Node(70);
		
		// **** build the binary tree ****
		BinaryTree tree = new BinaryTree(38);
		Node root 		= tree.getRoot();
		
		tree.add(root, n1, ChildLocation.LEFT);
		tree.add(root, n5, ChildLocation.RIGHT);
		
		tree.add(n1, n2, ChildLocation.LEFT);
		tree.add(n1, n3, ChildLocation.RIGHT);
		
		tree.add(n2, n4, ChildLocation.RIGHT);
		
		tree.add(n5, n6, ChildLocation.LEFT);
		tree.add(n5, n7, ChildLocation.RIGHT);
		
		tree.add(n7, n8, ChildLocation.RIGHT);
		
		
/*		
		// **** ****
		int[] values = {1, 2, 3, 4};
		System.out.println("main <<< values.length: " + values.length);

		// **** build the binary tree as illustrated here ****
		BinaryTree tree = new BinaryTree(10);
		Node root 		= tree.getRoot();
		
		tree.add(root, n1, ChildLocation.LEFT);
		tree.add(root, n2, ChildLocation.RIGHT);
		
		tree.add(n1, n3, ChildLocation.LEFT);
		tree.add(n1, n4, ChildLocation.RIGHT);
		
		tree.add(n2, n5, ChildLocation.LEFT);
		tree.add(n2, n6, ChildLocation.RIGHT);
		
		tree.add(n4, n7, ChildLocation.LEFT);
		
		tree.add(n6, n8, ChildLocation.RIGHT);
*/
		
		
		// **** depth first - preorder (root comes first) ****
		System.out.println("main <<< pre order:");
		tree.preOrder(root);
		
		// **** depth first - inorder (root is middle) ****
		System.out.println("\nmain <<< in order:");
		tree.inOrder(root);

		// **** depth first - inorder (using stack) ****
		System.out.println("\nmain <<< DFSInOrder:");
		tree.DFSInOrder(root);
		
		// **** depth first - postorder (root is last) ****
		System.out.println("\nmain <<< post order:");
		tree.postOrder(root);
		
		// **** depth first - postorder (using stack)
		System.out.println("\nmain <<< DFSPostOrder:");
		tree.DFSPostOrder(root);

		// **** breadth first using queue ****
		System.out.println("\nmain <<< BFS:");
		tree.BFS(root);
		
		// **** mystery order ****
		System.out.println("\nmain <<< MysteryOrder:"); tree.MysteryOrder(root); System.out.println(); // **** search for the specified value **** int value = 0; do { // **** prompt for the value to search for **** System.out.print(">>> value [-1 to exit]: ");
			value = sc.nextInt();
			
			// **** search for the specified value (if needed) ****
			if (value >= 0) {
				boolean found = tree.search(root, value);
				System.out.println("main <<< value: " + value + " found: " + found); } } while (value >= 0);
		
		// **** close scanner ****
		sc.close();
	}

}

Please note that I have written BST scaffolding a few times. You can find several posts in this blog that deal with BSTs. To write this post I searched for the BinaryTrees project which I located in workspace4 of the Eclipse IDE in my Windows computer. Please disregard commented out code.

Given that we will be interacting with the program to specify values to search in the BST, we first open a scanner. We then allocate a set of nodes to match the previous diagram. The root of the BST is instantiated and the nodes are added. I seems like all is well so far.

As I mentioned I wrote the method of interest in this existing project. Just o make sure the BST was properly built, I called a set of methods to display the BST while it is traversed in different ways. The BFS call towards the end of the initial display which follows is probably the simplest way to associate the diagram with the output.

main <<< pre order:
value: 38
value: 13
value: 26
value: 27
value: 30
value: 40
value: 56
value: 65
value: 70

main <<< in order:
value: 13
value: 26
value: 27
value: 30
value: 38
value: 40
value: 56
value: 65
value: 70

main <<< DFSInOrder:
value: 13
value: 26
value: 27
value: 30
value: 38
value: 40
value: 56
value: 65
value: 70

main <<< post order:
value: 13
value: 26
value: 27
value: 30
value: 40
value: 56
value: 65
value: 70
value: 38

main <<< DFSPostOrder:
value: 26
value: 13
value: 30
value: 27
value: 40
value: 70
value: 65
value: 56
value: 38

main <<< BFS:
38 
27 56 
13 30 40 65 
26 70 

main <<< MysteryOrder: 38 56 27 30 13 65 40 70 26 >>> value [-1 to exit]: 

We are now ready to enter some values and see if we can find them or not in the BST.

>>> value [-1 to exit]: 37
main <<< value: 37 found: false >>> value [-1 to exit]: 38
main <<< value: 38 found: true >>> value [-1 to exit]: 39
main <<< value: 39 found: false >>> value [-1 to exit]: 26
main <<< value: 26 found: true >>> value [-1 to exit]: 27
main <<< value: 27 found: true >>> value [-1 to exit]: 28
main <<< value: 28 found: false >>> value [-1 to exit]: 29
main <<< value: 29 found: false >>> value [-1 to exit]: 30
main <<< value: 30 found: true >>> value [-1 to exit]: 31
main <<< value: 31 found: false >>> value [-1 to exit]: 55
main <<< value: 55 found: false >>> value [-1 to exit]: 56
main <<< value: 56 found: true >>> value [-1 to exit]: 57
main <<< value: 57 found: false >>> value [-1 to exit]: 69
main <<< value: 69 found: false >>> value [-1 to exit]: 70
main <<< value: 70 found: true >>> value [-1 to exit]: 71
main <<< value: 71 found: false >>> value [-1 to exit]: -1

I have edited the output by adding blank lines in order to make it simpler to follow. We first try testing the root by searching for 37, 38 and 39. We then test n1 by searching for 26, 27, and 28. Note that 26 is the value associated with n4. We repeat the process using the values for n5 and n8. We then enter -1 to exit. All seems to work well.

package canessa.tree.ops;

public class Node {

	// **** members ****
	int 	value;
	Node 	left;
	Node 	right;
	
	Node	parent;
	int		level;
	
	/*
	 * constructor(s)
	 * Root level is zero (0).
	 */
	public Node(int value) {
		this.value 	= value;
		this.left	= null;
		this.right	= null;
		
		this.parent = null;
		this.level 	= 0;
	}
	
	/*
	 * Display the specified node.
	 */
	public void displayNode() {
		System.out.println("value: " + value);
	}
	
	/*
	 * Generate a string with the contents of the node.
	 */
	public String toString() {
		return "" + this.value;
	}
}

The Node class contains more fields that we need to implement the search method. We only need value, left and right. Please disregard the other two.

package canessa.tree.ops;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/*
 * 
 */
enum ChildLocation {
	LEFT,
	RIGHT
}

/*
 * Breadth first is a queue, depth first is a stack.
 */
public class BinaryTree {

	// **** ****
	private Node root;
	
	/*
	 * constructor
	 */
	public BinaryTree(int value) {
		Node root = new Node(value);
		this.root = root;
	}
	
	/*
	 * return the root of the binary tree
	 */
	public Node getRoot() {
		return this.root;
	}
	
	/*
	 * add a node to the binary tree
	 */
	public void add(Node parent, Node child, ChildLocation location) {
		
		// **** set level in child node ****
		child.level = parent.level + 1;
		
		// **** insert the child at the specified location ****
		if (location == ChildLocation.LEFT) {
			parent.left = child;
		} else {
			parent.right = child;
		}
	}
	
	/*
	 * in order traversal
	 * left - root - right
	 */
	public void inOrder(Node n) {
		if (n != null) {
			inOrder(n.left);
			n.displayNode();
			inOrder(n.right);
		}
	}
	
	/*
	 * post order traversal
	 * left - right - root
	 */
	public void postOrder(Node n) {
		if (n != null) {
			inOrder(n.left);
			inOrder(n.right);
			n.displayNode();
		}
	}
	
	/*
	 * pre order traversal
	 * root - left - right
	 */
	public void preOrder(Node n) {
		if (n != null) {
			n.displayNode();
			inOrder(n.left);
			inOrder(n.right);
		}
	}
	
	/*
	 * This method implements a breadth-first search traversal of a binary tree.
	 * This method is not recursive.
	 * It displays all nodes at each level on a separate line.
	 */
	public void BFS(Node root) {
		List<Node> currentQ = new LinkedList<Node>();
		List<Node> nextQ	= new LinkedList<Node>();
		
		currentQ.add(root);
		
		while (!currentQ.isEmpty()) {
			Node n = currentQ.remove(0);
			System.out.print(n.toString() + " ");
			
			if (n.left != null)
				nextQ.add(n.left);
			if (n.right != null)
				nextQ.add(n.right);
			
			// **** check if end of current level ****
			if (currentQ.isEmpty()) {
				System.out.println();
				currentQ = nextQ;
				nextQ = new LinkedList<Node>();
			}
		}
		
	}
	
	/*
	 * Similar to BFS but using stacks.
	 * Does not seem to provide a known order.
	 */
	public void MysteryOrder(Node root) {
		Stack<Node> currentS 	= new Stack<Node>();
		Stack<Node> nextS 		= new Stack<Node>();
		
		currentS.push(root);
		
		while(!currentS.isEmpty()) {
			Node n = currentS.pop();
			System.out.print(n.toString() + " ");
			
			if (n.left != null)
				nextS.push(n.left);
			if (n.right != null)
				nextS.push(n.right);
		
			// **** ****
			if (currentS.isEmpty()) {
				System.out.println();
				currentS = nextS;
				nextS	 = new Stack<Node>();
			}
		}
	}

	/*
	 * 
	 */
	public void DFSInOrder(Node root) {
		Stack<Node> s 	= new Stack<Node>();
		Node n 			= root;
		
		while ((n != null) || (s.size() > 0)) {
			
	        while (n !=  null) { 
	            s.push(n); 
	            n = n.left; 
	        } 			

            n = s.pop(); 
            n.displayNode();
            n = n.right; 
		}
	}
	
	/*
	 * 
	 */
	public void DFSPostOrder(Node root)  
    { 
        Stack<Node> stack 	= new Stack<Node>(); 
        stack.push(root); 
        Node prev 			= null;
        
        while (!stack.isEmpty())  { 
            Node n = stack.peek(); 
   
            if (prev == null || prev.left == n || prev.right == n) { 
                if (n.left != null) 
                    stack.push(n.left); 
                else if (n.right != null) 
                    stack.push(n.right); 
                else { 
                    stack.pop(); 
                    n.displayNode();
                } 
            }  else if (n.left == prev) { 
                if (n.right != null) 
                    stack.push(n.right); 
                else { 
                    stack.pop(); 
                    n.displayNode();
                }                    
            } else if (n.right == prev)  { 
                stack.pop(); 
                n.displayNode(); 
            } 
            prev = n; 
        } 
    }
	
	/*
	 * Search the BST for the specified value.
	 */
	public boolean search(Node root, int val) {
		
		boolean found = false;
		
		// **** check if we found the value ****
		if (root.value == val)
			return true;
		
		// **** search the left tree (if needed) ****
		if (root.left != null)
			found = search(root.left, val);

		// **** search the right tree (if needed) ****
		if (!found && (root.right != null))
			found = search(root.right, val);
		
		// **** ****
		return found;
	}
}

In the BinaryTree class we have the methods that we used to build the BST and display. I believe most if not all methods are self explained and I have covered them in previous posts.

Of interest if the last method named search(Node root, int val). We specify a root node and the value to search. This is a recursive method. In the main() code we invoke the method and pass it the BST root. Inside the search() method we declare a variable to flag if the value we are looking for is found or not.

If as we traverse the BST we find the value the search() method returns true. We are done with the search. If not found we try the left child. When the traversal of the left tree is completed, we check if we have not found the value. If we have a right child we continue our search. When all is set and done we return a Boolean value to indicate the state of affairs.

I want to add that I work using the Work Deep techniques. In a nutshell when I get up at or before 05:00 AM every day of a year, I power up one or more computers and concentrate on the first task in my To Do List. Two hours later I get up, walk and refresh my drink. I walk for 5 to 10 minutes and repeat. The idea is to be able to work 8 to 10 hours a workday and 4 to 6 hours on weekends. It is hard for me to concentrate well past the first three 2-hour blocks. The good thing is that in general I get more work done in a day than most people. If interested in this technique I recommend you to read the book by Cal Newport. You can purchase it from Amazon.

Note that I developed and tested this piece of code in about 15 minutes and did not use a whiteboard to write code and then copied it to the IDE. I used the TDD approach. The rest of the time was working with Visio, creating the text for this blog, using WordPress to create the actual post, insert the code and look for pictures. That said, as soon as the whiteboard and book arrive next week, I will start using the whiteboard and learn if it has any benefits.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.

Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.