A binary tree is a data structure in which each node can have between 1 and 2 children. Here is an example of one:

The 8 here is the ‘root’ of the tree, and the bottom of the tree consists of the ‘leaves’ (which have no children). In this case, we call this type of binary tree a **Binary Search Tree**. This is because each parent is greater than or equal to its left child, and its right child is greater than or equal to the parent. This makes traversing the tree extremely easy and also makes it’s search complexity time O(log n). We’re in essence, halving the search space with every iteration downward.

Each node is almost like a LinkedList, however instead of just containing one ‘next’ item, they contain two (a right and left child). Let’s get started by coding a Node for a binary tree.

class Node { // the key is used to compare nodes int key; // this is the data each node stores String value; // binary tree's have nodes that can contain // a left child, a right child or both Node leftChild; Node rightChild; // we require a key and a value to create a node Node(int key, String value) { this.key = key; this.value = value; } public String toString() { return "key: " + key + "value: " + value; } }

If you’re familiar with LinkedLists from the previous sections, this should be pretty straight forward for you. Now is where things change up a bit – the BinaryTree class:

class BinarySearchTree{ Node root; public void addNode(int key, String value){ // Create a new Node and initialize it Node newNode = new Node(key, name); // If there is no root this becomes root if (root == null) { root = newNode; } else { // Set root as the Node we will start // with as we traverse the tree Node focusNode = root; // future parent for new Node Node parent; while(true){ //root is the parent, so we start there parent = focusNode; //check if we should go left or right if(key < focusNode.key){ focusNode = focusNode.leftChild; // if the left child has no children if(focusNode == null){ // then place the new node on the left of it parent.leftChild = newNode; return; } } else { // if we get here, put it on the right focusNode = focusNode.rightChild; if(focusNode == null){ parent.rightChild = newNode; return; // done } } } } } }

Now we have a surefire way to add nodes into the correct places of our BinarySearchTree! Pretty simple actually, if you just follow the logic through. The key is to remember the bigger goal. Now, what about traversing the tree?

Well, there’s 3 ways. Pre-order, in-order and post-order traversal. Let’s do into what each of these mean in detail.

### Pre-Order Traversal

public void preorderTraverseTree(Node focusNode) { if (focusNode != null) { System.out.println(focusNode); preorderTraverseTree(focusNode.leftChild); preorderTraverseTree(focusNode.rightChild); } }

Pre-order traversal goes from the root to the left side and explores that side first. Once it reaches the end of the left side, it does the same on the right.

### In-order Traversal

public void inOrderTraverseTree(Node focusNode) { if (focusNode != null) { // Traverse the left node inOrderTraverseTree(focusNode.leftChild); // Visit the currently focused on node System.out.println(focusNode); // Traverse the right node inOrderTraverseTree(focusNode.rightChild); } }

In-order traversal iterates through the lowest, to the highest keys. See the diagram above.

### Post-order Traversal

public void postOrderTraverseTree(Node focusNode) { if (focusNode != null) { postOrderTraverseTree(focusNode.leftChild); postOrderTraverseTree(focusNode.rightChild); System.out.println(focusNode); } }

Post-order traversal explores the left side starting with the leaves first and works its way up to the root. After it hits the root node, it does the same thing on the right side.

Now let’s put all of our knowledge to work with a practice question from ‘Cracking the Coding Interview’.

Implement a function to check if a binary tree is a binary search tree.

This question is easy. All we have to do is iterate down the tree in pre-order traversal while checking if:

leftNode <= currentNode < rightChild

If that check is ever violated, we immediately return a false value.

public static int last_printed = Integer.MIN_VALUE; public static boolean checkBST(BinarySearchTree t){ if(t == null) return true; // check / recurse left if(!checkBST(t.leftChild)) return false; //check current if(t.value <= last_printed) return false; // check / recurse right if(!checkBST(t.rightChild)) return false; return true; // DONE! }

## Leave a Reply