Home



2020/03 - DS&A #11: Binary Tree

Howdy folks!

Today we'll be looking at how the Binary Tree works. We also need an additional class, a Binary Tree Node class because our nodes are just values this time, they contain additional data required by the Binary Tree in order for it to operate. We'll start off first with the building blocks of the binary tree, the node:

 

 

public class BinaryTreeNode implements Comparable{
    
    Integer value;
    BinaryTreeNode left;
    BinaryTreeNode right;
    BinaryTreeNode parent;
    
    public static enum NodeSide {
        LEFT,
        RIGHT
    }
    
    public NodeSide determineChildSide() {
        if(this.parent.left == this) {
            return NodeSide.LEFT;
        }
        else {
            return NodeSide.RIGHT;
        }
    }
    
    public BinaryTreeNode(Integer value) {
        this.value = value;
    }
    
    public Integer getValue() {
        return value;
    }
    
    public void setValue(Integer value) {
        this.value = value;
    }
    
    public BinaryTreeNode getLeft() {
        return left;
    }
    
    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }
    
    public BinaryTreeNode getRight() {
        return right;
    }
    
    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }
    
    public BinaryTreeNode getParent() {
        return parent;
    }
    
    public void setParent(BinaryTreeNode parent) {
        this.parent = parent;
    }

    @Override
    public int compareTo(Object o) {
        BinaryTreeNode comparedUpon = (BinaryTreeNode) o;
        int gtoet = 0;
        if(comparedUpon.value > this.value) {
            gtoet = 1;    
        }
        else if(comparedUpon.value < this.value) {
            gtoet = -1;        
        }
        return gtoet;
    }
    
    public String toString() {
        return this.value.toString();
    }

}

 

A binary tree consist of a bunch of nodes all linking back to one another, similarly to how a linkedList might point to it's next node. In the binary tree's case however, each node is not set up in a sequential fashion (e.g. ELEMENT -> ELEMENT -> ELEMENT -> and so on), but rather it is set up in a tree-like format:

 

 

As you can see, each element (or node) points to two node beneath itself. The child node on the left is called the nodes left, the child node on the right is the nodes right node, the node above is the nodes parent, and the node itself contains a reference to each of these three nodes as well as a value (In our case, a number). The binary node class contains a couple more methods of interest to us, the toString method for the sake of formatting and a compareTo method that allows the binary tree to compare node values.

Up next we have the (Comparatively to our last few posts' classes) much larger binary tree class itself. Before going ahead with this, it should be mentioned that the child node values need to be ordered correctly for a binary tree to "work". The left child should have a value lower than the parents value, and the right child should have a value greater than the parents value.

 

public class BinaryTree {
        
    BinaryTreeNode rootNode;
        
    //Finding data with pre-order traversal
    public BinaryTreeNode findNodePreOrder(BinaryTreeNode valueToCompare, BinaryTreeNode valueToFind) {
        
        BinaryTreeNode foundValue = null;
        
        if(valueToCompare != valueToFind) {
            System.out.println(valueToCompare + " is not " + valueToFind);
            if(valueToCompare.left != null) {
                findNodePreOrder(valueToCompare.left, valueToFind);
            }
            if(valueToCompare.right != null) {
                findNodePreOrder(valueToCompare.right, valueToFind);
            }
        }
        else {
            System.out.println(valueToCompare + " Found!");
            foundValue = valueToCompare;
        }        
        
        return foundValue;
                 
    }
    

A note on exactly how "finding a node works" and how each of the finding methods are different. The way we find nodes involves three steps:

  1. Evaluate current node
  2. Visit left child (And evaluate recursively)
  3. Check right child (And evaluate recursively)

The order in which we do this affects the performance of the binary tree search, which is the whole point of even using this data structure to begin with. We've meshed our tree traversal and the finding method together here to give you an idea of how both work. The above code performs a pre-order search, which means that it first evaluates the current node, then tries the left child, then checks the right. If the value we're searching for is a high value, this search will perform badly, but if it's a low value it should be faster (This example is pretty rudimentary, go to a math class if you want to see how complex this can get!)

 

    //This is an additional example of in order traversal that uses a stack to avoid runtime out-of-memory exceptions
    public void InOrderStackTraversal() {
        
        if (rootNode != null) {

            Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
            BinaryTreeNode current = rootNode;
            boolean goLeftNext = true;

            stack.push(current);

            while (stack.size() > 0) {
                if (goLeftNext) {
                    while (current.left != null) {
                        stack.push(current);
                        current = current.left;
                    }
                }

                System.out.println(current.value);

                if (current.right != null) {
                    current = current.right;
                    goLeftNext = true;
                }
                else {
                    current = stack.pop();
                    goLeftNext = false;
                }
            }
        }
    }
    

The above is a stack-based approach to the in-order traversal method, which performs evaluation in the following order:

  1. Left
  2. Current
  3. Right

 

    //Finding data with in-order traversal
    public BinaryTreeNode findNodeInOrder(BinaryTreeNode valueToCompare, BinaryTreeNode valueToFind) {
        
        BinaryTreeNode foundValue = null;
        if(valueToCompare.left != null) {
            findNodeInOrder(valueToCompare.left, valueToFind);
        }
        
        if(valueToCompare.value != valueToFind.value) {
            System.out.println(valueToCompare + " is not " + valueToFind);
            if(valueToCompare.right != null) {
                findNodeInOrder(valueToCompare.right, valueToFind);
            }
        }
        else {
            foundValue = valueToCompare;
            System.out.println(valueToCompare + " was finally found!");
        }        
        
        return foundValue;
                 
    }

The same traversal mechanism again, just not using a stack this time.

 

    //Finding data with post-order traversal
    public BinaryTreeNode findNodePostOrder(BinaryTreeNode valueToCompare, BinaryTreeNode valueToFind) {
        
        BinaryTreeNode foundValue = null;
        if(valueToCompare.left != null) {
            findNodePostOrder(valueToCompare.left, valueToFind);
        }
        if(valueToCompare.right != null) {
            findNodePostOrder(valueToCompare.right, valueToFind);
        }
        
        if(valueToCompare.value == valueToFind.value){
            System.out.println(valueToCompare + " is found!");
            foundValue = valueToCompare;
        }        
        else {
            System.out.println(valueToCompare + " is not " + valueToFind);
        }
        
        return foundValue;
                 
    }

Post order traversal travels in the following order:

  1. Left
  2. Right
  3. Current

 

    public BinaryTreeNode findNode(BinaryTreeNode valueToFind) {
        return findNodePostOrder(rootNode, valueToFind);    
        
    }

A convenience finding method. The order implementation can be changed by you if you simply change findNodePostOrder to another traversal/finding method.

 

 

    public void detachParentFromNode(BinaryTreeNode valueToDetach) {
        BinaryTreeNode parent = valueToDetach.parent;
        
        if(parent.left == valueToDetach) {
            parent.left = null;
        }
        else {    
            parent.right = null;
        }
    }

Detach a node from its parent, this is only in its own function for the sake of clean code.

 

    //Removing data
    public BinaryTreeNode removeNode(BinaryTreeNode currentValue, BinaryTreeNode valueToFind) {
        
        BinaryTreeNode removedNode = null;
        
        if(currentValue.value != valueToFind.value) {
            removeNode(valueToFind.left, valueToFind);
            removeNode(valueToFind.right, valueToFind);        
        }
        else {
            
            removedNode = currentValue;    
            //If leaf node it's simple. If it's not there are three scenarios to consider
            if(currentValue.left == null && currentValue.right == null) {
                this.detachParentFromNode(removedNode);
            }
            else if(currentValue.left != null && currentValue.right == null) {
                if(currentValue.determineChildSide() == BinaryTreeNode.NodeSide.LEFT) {
                    currentValue.parent.left = currentValue.left;    
                }
                else {
                    currentValue.parent.right = currentValue.left;
                }       
            }
            else if(currentValue.left !=  null && currentValue.right != null) {
                if(currentValue.right.left == null) {
                    BinaryTreeNode newLeft = currentValue.left;
                    BinaryTreeNode movedNode = currentValue.right;
                    movedNode.left = newLeft;
                    if(currentValue.determineChildSide() == BinaryTreeNode.NodeSide.LEFT) {
                        currentValue.parent.left = movedNode;    
                    }
                    else {
                        currentValue.parent.right = movedNode;    
                    }
                    
                }
                else {
                    BinaryTreeNode newLeft = currentValue.left;
                    BinaryTreeNode newRight = currentValue.right;
                    BinaryTreeNode movedNode = currentValue.right.left;
                    movedNode.right = newRight;
                    movedNode.left = newLeft;
                    if(currentValue.determineChildSide() == BinaryTreeNode.NodeSide.LEFT) {
                        currentValue.parent.left = movedNode;    
                    }
                    else {
                        currentValue.parent.right = movedNode;    
                    }
                }

            }
        }
        
        return removedNode;
    }

Removing a node from a sorted binary tree is honestly a bit of a pain. You have to preserve the integrity of the tree's sorted values, so you can't just remove nodes willy-nilly. There are three main scenarios that will happen when you try to remove a node:

  1. It'll be a leaf node, for which you can just detach it from its parent.
  2. It won't exist, so you can just exit
  3. It'll be a non-leaf node that exists, which means we're going to have to accomodate the children as per the following sub-list...

 

  1. If the removed node has no right child, just replace it with the left child
  2. If the removed node has no left child, just replace it with the right child
  3. (The trickiest scenario) If the removed nodes right child, has a left child, replace the node with that child (Yes, that's right.... Or left)

Removal makes sense if you think about it. It's a bit tricky to understand at first, but play around with the program and it'll be clear eventually.

 

    public void addNode(BinaryTreeNode currentNode, BinaryTreeNode newNode) {
        if(rootNode == null) {
            rootNode = newNode;
            addNode(rootNode, newNode);
        }
        else if(currentNode.value > newNode.value) {
            if(currentNode.left == null) {
                currentNode.left = newNode;
                newNode.parent = currentNode;
                System.out.println("Assigned " + newNode + " under " + currentNode + " as it's left node");
            }
            else {
                addNode(currentNode.left, newNode);      
            }
        }
        else if(currentNode.value <= newNode.value) {
            if(currentNode.right == null) {
                currentNode.right = newNode;
                newNode.parent = currentNode;
                System.out.println("Assigned " + newNode + " under " + currentNode + " as it's right node");
            }
            else {
                addNode(currentNode.right, newNode);      
            }
        }        
    }

Adding a node works in the following manner:

  1. If the tree is empty, assign the new node as the root node.
  2. If the new node is greater than or equal to the node we're adding it to, it takes up the right child space.
  3. If the new node is lower, add it to the left instead.

 

    public void addNode(BinaryTreeNode newNode) {
        if(rootNode == null) {
            rootNode = newNode;
        }
        else {
            addNode(rootNode, newNode);
        }    
        
    }

A convenience method for adding nodes. The code block above this one actually performs recursively until it finds the correct child node to take up, so we aren't necessarily just adding a node to the root node.

 

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        
        //Stack intead of recursion when traversing, because recursion could cause stack
        //overflow errors in production
        bt.addNode(new BinaryTreeNode(4));
        bt.addNode(new BinaryTreeNode(2));
        bt.addNode(new BinaryTreeNode(1));
        bt.addNode(new BinaryTreeNode(6));
        bt.addNode(new BinaryTreeNode(7));
        bt.addNode(new BinaryTreeNode(3));
        bt.addNode(new BinaryTreeNode(5));
        
        //bt.InOrderStackTraversal();
        bt.findNode(new BinaryTreeNode(5));
        
        
    /*    bt.addNode(new BinaryTreeNode(1));
        bt.addNode(new BinaryTreeNode(2));
        bt.addNode(new BinaryTreeNode(3));
        bt.addNode(new BinaryTreeNode(4));
        bt.addNode(new BinaryTreeNode(5));
        bt.addNode(new BinaryTreeNode(6));
        bt.addNode(new BinaryTreeNode(7));
        bt.addNode(new BinaryTreeNode(8));*/
        
    }

}

 

Finally we have our main method along with a few pieces of test data for you to use in order to see the binary tree in action.

And that about wraps it up for the binary tree. It's a bit more involved than the previous sorting tutorials I've been posting so far, but hey, employers have to interview you using SOMETHING right?

Good luck!

Marc