Introduction
- Lets do some computer science in Java!!
Video version
GitHub code
What we are doing
- Before you dive into this, you should have a basic understanding on how recursion works
- Today we are going to talk about Binary Search Trees and how to traverse them. We are going to be looking at depth first traversal and the breadth first traversal. But before we go any further lets talk a little about trees in general
Trees
- A quick run down on trees is that they are a non-linear data structure made up of nodes(we will elaborate on nodes when we start building a tree) that must abide by these three general rules:
1) Each tree has a root node
2) The root node has zero or more children
3) Each child node has zero or more child nodes and so one
- Now there are several different types of trees but we we are specifically interested in Binary Search Trees (BST).
Binary Tree
- A
Binary Tree(BT) is a tree in which each node has up to two children. Which is not the norm for all trees. In fact aTernary Treeis a type of tree where each node has three children. So any time we see a Tree data structure that has Binary in its name, we know that each of it's nodes has at most 2 children. - Ok then what is the difference between a Binary Search Trees and a Binary Tree?
Binary Search Trees
- A BST differs from a BT in the face that every individual node fits the specific ordering:
left descendants <= n all right descendants for each node n. What that means is that all children left of a node will be less than it and all the children right of the node will be greater than it. A BST looks like this
- notice the ordering of the numbers. A BT does not have to keep that ordering.
Unbalanced vs Balanced trees
- Now if you have read about trees at all then you have probably heard about balancing and that you should make sure your trees are balanced. Which is true, an unbalanced BST loses all of it's search efficiencies. However, to keep things simple we are not going to be talking about how to balance a tree, that will be in a later post when we talk bout
AVLtrees. Instead we are just going to make a simple tree that will allow us to traverse it.
Binary Search Tree implementation
- Creating and implementing our simple BST can be broken down into 4 steps
1) create the node
2) create insert method
3) create depth first methods
4) create breadth first method
1) create the node
- For the sake of simplicity and ease of use we are going to nest a Node class inside of our BST class, it will look something like this: ```
public class BinarySearchTree {
private int size = 0;
private Node root = null;
protected class Node{
private int element;
private Node leftChild;
private Node rightChild;
public Node(int element,Node leftChild, Node rightChild){
this.element = element;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
//GETTERS
public int getElement(){
return this.element;
}
public Node getLeftChild(){
return this.leftChild;
}
public Node getRightChild(){
return this.rightChild;
}
//SETTERS
public void setElement(int element) {
this.element = element;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
}
}
- As you can see the Node class is really just a basic [POJO](https://en.wikipedia.org/wiki/Plain_old_Java_object) and all it holds is an element and a reference to two child nodes.
- You will also notice that we are also keeping track of the first node inserted(the root) and giving it an initial value of null, `private Node root = null`. This is crucial because it will be used by our methods to determine if there are any nodes to traverse
#### 2) create insert method
- This insert method is not going to be too complicated, but just remember that when inserting a Node it must abide by this ordering specification: `left decendants <= n < right decendants for each node n`. Now we are also going to break this insert method up into two different methods. With that being said lets create the first method:
public void insert(int item){
Node newNode = new Node(item,null,null);
if(root == null){
root = newNode;
}else{
insertNode(this.root,newNode);
}
this.size ++;
}
- If the root is null, that means the tree is empty and we add a new node as the root. If the root is not null we call the `insertNode(this.root,newNode)` with the root and the newNode. The `insertNode` method is where the majority of the work is going on. So the method looks like this:
private void insertNode(Node node,Node newNode){
if(newNode.element < node.element){
if (node.getLeftChild() == null){
node.setLeftChild(newNode);
}else{
insertNode(node.getLeftChild(),newNode);
}
}else{
if(node.getRightChild() == null){
node.setRightChild(newNode);
}else{
insertNode(node.getRightChild(),newNode);
}
}
}
- The first conditional, `newNode.element < node.element` is used to check which side of the current node our new node belongs on. If the conditional is true, that means it belongs on the left side, if it is false, it belongs on the right side. This conditional also acts as our base case for the recursion:
if (node.getLeftChild() == null){
node.setLeftChild(newNode);
}else{
insertNode(node.getLeftChild(),newNode);
}
}
- This conditional is used to determine if we have found the place where our node goes or if we need to keep traversing the tree. The `insertNode(node.getLeftChild(),newNode)` method is a recursive method call.
- The second conditional:
else{
if(node.getRightChild() == null){
node.setRightChild(newNode);
}else{
insertNode(node.getRightChild(),newNode);
}
}
- The code above is the exact mirror of our previous code, meaning that this code is run when `newNode.element < node.element`
- So now that we have our insertion method up and running, lets start traversing.
####3) create depth first methods
- Now Depth-first traversal DFT is a method for exploring a tree or graph. In a DFT, you go as deep as possible down one path before backing up and trying a different one.
- There are 3 different approaches to a depth first traversal:
**1)in-order**
**2)pre-order**
**3)post-order**
##### in-order traversal
- A in-order traversal visits all the nodes of a BST in ascending order. which means it visits the nodes from the smallest to the largest and its implementation looks like this:
public void inOrderTraversal(){
inOrderTraversalNode(this.root);
}
private void inOrderTraversalNode(Node node){
if(node != null){
inOrderTraversalNode(node.getLeftChild());
System.out.println(node.element);
inOrderTraversalNode(node.getRightChild());
}
}
- First I want you to notice that yet again we are breaking things up into two methods. This time it is for ease of use, so we can simply call the `inOrderTraversal()` method without having to pass it the root node.
- Then if we look at the `inOrderTraversalNode(Node node)` method notice how we are using recursion and how weirdly simple it is.
- You will see in the `pre` and `post` traversal methods the only difference between these methods is where we put the action or in our case the: `System.out.println(node.element)`.
##### pre-order traversal
- A pre-order traversal visits the node prior to its descendants, which sounds a little confusing but the code clears things:
public void preOrderTraversal(){
preOrderTraversalNode(this.root);
}
private void preOrderTraversalNode(Node node){
if(node != null){
System.out.println(node.element);
inOrderTraversalNode(node.getLeftChild());
inOrderTraversalNode(node.getRightChild());
}
}
##### post-order traversal
- Post order traversal visits the node after it visits descendants:
public void postOrderTraversal(){
postOrderTraversalNode(this.root);
}
private void postOrderTraversalNode(Node node){
if(node != null){
inOrderTraversalNode(node.getLeftChild());
inOrderTraversalNode(node.getRightChild());
System.out.println(node.element);
}
}
- These methods are nothing too complicated. However, the breadth first traversal does get a little complicated
### Breadth first traversal
- Another approach is to traverse a tree so that we visit all the positions at depth d before we visit the positions at d + 1.
- This traversal algorithm is not recursive, since we are not traversing the entire tree at once. We will use a Queue for its `first in first out` order in which we visit the nodes. This method can get a little confusing so I have broken it down into 6 parts:
**1) define the returned list**
**2) check if the root is empty**
**3) create internal queue and add the root**
**4) while loop for non empty queue**
**5) run the children() method**
**6) return the list**
- As you can see this is quite a few steps but lets get started:
#### 1) define the returned list
public List breadthFirstSearch(){
List breadthList = new ArrayList<>();
}
- We start off with defining our method, which is going to return a List<Node>. This list is going to contain all the nodes in a proper breadth first order.
#### 2) check if the root is empty
public List breadthFirstSearch(){
List breadthList = new ArrayList<>();
if(this.root == null){
return null;
}else{
}
}
- This section is just a simple conditional check to determine if the root is null. If it is null we just return null, if it is not null we enter the else conditional where we will do the actual traversal.
#### 3) create internal queue and add the root
public List breadthFirstSearch(){
//all previous code included
else{
Queue queue = new LinkedList();
queue.add(this.root);
}
}
- Since the queue is just an interface in Java we can use polymorphism and instantiate it with a LinkedList. Then we add the root to the queue.
#### 4) while loop for non empty queue
public List breadthFirstSearch(){
//all previous code included
else{
Queue queue = new LinkedList();
queue.add(this.root);
while(!queue.isEmpty()){
Node node = queue.remove();
breadthList.add(node);
}
}
- Now we create a while loop that will run as long as the queue is not empty. Inside of that while loop we remove the first node inside of our queue, `Node node = queue.remove()`. Then we add it to the list we are going to return `breadthList.add(node);`.
#### 5) run the children() method
public List breadthFirstSearch(){
//all previous code included
else{
Queue queue = new LinkedList();
queue.add(this.root);
while(!queue.isEmpty()){
Node node = queue.remove();
breadthList.add(node);
//notice the children() method
for (Node n:children(node)){
queue.add(n);
}
}
}
- So look at the for loop we have created:
for (Node n:children(node)){
queue.add(n);
}
- This loop is actually what keeps our while loop going and adding to the queue. Ok but what exactly is the children method?
private List children(Node node){
List list = new ArrayList<>(2);
if(node.getLeftChild() != null){
list.add(node.getLeftChild());
}
if(node.getRightChild() != null){
list.add(node.getRightChild());
}
return list;
}
- Its a very simple method that checks if the node it is called with has any children and if it does it returns a list with those children. Then thanks to the previously mentioned for loop, those children get added to the queue
#### 6) return the list
- Last thing we do is have our method return the `breadthList` that contains the properly ordered nodes:
public List<Node> breadthFirstSearch(){
List<Node> breadthList = new ArrayList<>();
if(root == null){
return null;
}else{
Queue<Node> queue = new LinkedList();
queue.add(this.root);
while(!queue.isEmpty()){
Node node = queue.remove();
breadthList.add(node);
for (Node n:children(node)){
queue.add(n);
}
}
}
return breadthList;
}
###Conclusion
- Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on [Twitter](https://twitter.com/AndroidTristan).
Top comments (2)
Had a quick check on your repo. First, mind your impl is not thread-safe, as in some cases(like mid to huge trees), utilizing threads in right manner could help too much.
Same, I could not bear with some of statements, like following:
As I would declare
breadthListwhen it's really needed, not by default.Also I would come up with something like
children(:Node,:List<Node>):List<Node>, which allows giving a "working"(temp) list, instead of creating one for each call(creating a new, whennull). Or even better, pass aQueue, instead ofList.Ok, Thank you!!!!! do you have any resources on Thread-safe trees? Or just any extra resources to read in general?