A binary tree is a tree that has a maximum of two children per node. The two children can be called the left and the right child of a node. The following figure shows an example of a binary tree:
Example binary tree
This particular tree is important mostly because of its simplicity. We can create a BinaryTree class by inheriting the general tree class. However, it will be difficult to stop someone from adding more than two nodes and will take a lot of code just to perform the checks. So, instead, we will create a BinaryTree class from scratch:
public class BinaryTree<E> {The Node has a very obvious implementation just like the generic tree:
public static class Node<E>{
private E value;
private Node<E> left;
private Node<E> right;
private Node<E> parent;
private BinaryTree<E> containerTree;
protected Node(Node<E> parent,
BinaryTree<E> containerTree, E value) {
this.value = value;
this.parent = parent;
this.containerTree = containerTree;
}
public E getValue(){
return value;
}
}Adding the root is exactly the same as that for a generic tree, except for the fact that we don't check for the existence of the root. This is just to save space; you can implement as required:
private Node<E> root;
public void addRoot(E value){
root = new Node<>(null, this, value);
}
public Node<E> getRoot(){
return root;
}The following method lets us add a child. It takes a Boolean parameter that is true when the child to be added is the left child and false otherwise:
public Node<E> addChild(Node<E> parent, E value, boolean left){
if(parent == null){
throw new NullPointerException("Cannot add node to null parent");
}else if(parent.containerTree != this){
throw new IllegalArgumentException
("Parent does not belong to this tree");
}else {
Node<E> child = new Node<E>(parent, this, value);
if(left){
parent.left = child;
}else{
parent.right = child;
}
return child;
}
}We now create two wrapper methods for specifically adding either the left or the right child:
public Node<E> addChildLeft(Node<E> parent, E value){
return addChild(parent, value, true);
}
public Node<E> addChildRight(Node<E> parent, E value){
return addChild(parent, value, false);
}
}Of course, the traversal algorithms for a generic tree would also work for this special case. However, for a binary tree, the depth-first traversal can be of three different types.
The depth-first traversal of a binary tree can be of three types according to when the parent node is processed with respect to when the child subtrees are processed. The orders can be summarized as follows:
- Pre-order traversal:
- In-order traversal:
- Post-order traversal:
These different traversal types will produce a slightly different ordering when traversing:
public static enum DepthFirstTraversalType{
PREORDER, INORDER, POSTORDER
}
public void traverseDepthFirst(OneArgumentStatement<E> processor,
Node<E> current, DepthFirstTraversalType tOrder){
if(current==null){
return;
}
if(tOrder == DepthFirstTraversalType.PREORDER){
processor.doSomething(current.value);
}
traverseDepthFirst(processor, current.left, tOrder);
if(tOrder == DepthFirstTraversalType.INORDER){
processor.doSomething(current.value);
}
traverseDepthFirst(processor, current.right, tOrder);
if(tOrder == DepthFirstTraversalType.POSTORDER){
processor.doSomething(current.value);
}
}We have created an enum DepthFirstTraversalType to pass to the traverseDepthFirst method. We process the current node according to its value. Note that the only thing that changes is when the processor is called to process a node. Let's create a binary tree and see how the results differ in the case of each ordering:
public static void main(String [] args){
BinaryTree<Integer> tree = new BinaryTree<>();
tree.addRoot(1);
Node<Integer> n1 = tree.getRoot();
Node<Integer> n2 = tree.addChild(n1, 2, true);
Node<Integer> n3 = tree.addChild(n1, 3, false);
Node<Integer> n4 = tree.addChild(n2, 4, true);
Node<Integer> n5 = tree.addChild(n2, 5, false);
Node<Integer> n6 = tree.addChild(n3, 6, true);
Node<Integer> n7 = tree.addChild(n3, 7, false);
Node<Integer> n8 = tree.addChild(n4, 8, true);
Node<Integer> n9 = tree.addChild(n4, 9, false);
Node<Integer> n10 = tree.addChild(n5, 10, true);
tree.traverseDepthFirst(System.out::print, tree.getRoot(),
DepthFirstTraversalType.PREORDER);
System.out.println();
tree.traverseDepthFirst(System.out::print, tree.getRoot(),
DepthFirstTraversalType.INORDER);
System.out.println();
tree.traverseDepthFirst(System.out::print, tree.getRoot(),
DepthFirstTraversalType.POSTORDER);
System.out.println();
} We have created the same binary tree as shown in the previous figure. The following is the output of the program. Try to relate how the positions are getting affected:
1 2 4 8 9 5 10 3 6 7 8 4 9 2 10 5 1 6 3 7 8 9 4 10 5 2 6 7 3 1
You can take a note of the following points while matching the program output:
- In the case of a pre-order traversal, in any path starting from the root to any leaf, a parent node will always be printed before any of the children.
- In the case of an in-order traversal, if we look at any path from the root to a particular leaf, whenever we move from the parent to the left child, the parent's processing is postponed. But whenever we move from the parent to the right child, the parent is immediately processed.
- In the case of a post-order traversal, all the children are processed before any parent is processed.
The depth-first search we have seen for the general tree is pre-order in the sense that the parent node is processed before any of the children are processed. So, we can use the same implementation for the pre-order traversal of a binary tree:
public void traversePreOrderNonRecursive(
OneArgumentStatement<E> processor) {
Stack<Node<E>> stack = new StackImplLinkedList<>();
stack.push(getRoot());
while (stack.peek()!=null){
Node<E> current = stack.pop();
processor.doSomething(current.value);
if(current.right!=null)
stack.push(current.right);
if(current.left!=null)
stack.push(current.left);
}
}Implementation of the in-order and post-order traversals is a bit tricky. We need to suspend processing of the parent node even when the children are expanded and pushed to the stack. We can achieve this by pushing each node twice. Once, we push it when it is first discovered due to its parent being expanded, and the next time we do it when its own children are expanded. So, we must remember which of these pushes caused it to be in the stack when it's popped. This is achieved using an additional flag, which is then wrapped up in a class called StackFrame. The in-order algorithm is as follows:
public void traverseInOrderNonRecursive(
OneArgumentStatement<E> processor) {
class StackFame{
Node<E> node;
boolean childrenPushed = false;
public StackFame(Node<E> node, boolean childrenPushed) {
this.node = node;
this.childrenPushed = childrenPushed;
}
}
Stack<StackFame> stack = new StackImplLinkedList<>();
stack.push(new StackFame(getRoot(), false));
while (stack.peek()!=null){
StackFame current = stack.pop();
if(current.childrenPushed){
processor.doSomething(current.node.value);
}else{
if(current.node.right!=null)
stack.push(new StackFame(current.node.right, false));
stack.push(new StackFame(current.node, true));
if(current.node.left!=null)
stack.push(new StackFame(current.node.left, false));
}
}
}Note that the stack is LIFO, so the thing that needs to be popped later must be pushed earlier. The post-order version is extremely similar:
public void traversePostOrderNonRecursive(OneArgumentStatement<E> processor) {
class StackFame{
Node<E> node;
boolean childrenPushed = false;
public StackFame(Node<E> node, boolean childrenPushed) {
this.node = node;
this.childrenPushed = childrenPushed;
}
}
Stack<StackFame> stack = new StackImplLinkedList<>();
stack.push(new StackFame(getRoot(), false));
while (stack.peek()!=null){
StackFame current = stack.pop();
if(current.childrenPushed){
processor.doSomething(current.node.value);
}else{
stack.push(new StackFame(current.node, true));
if(current.node.right!=null)
stack.push(new StackFame(current.node.right, false));
if(current.node.left!=null)
stack.push(new StackFame(current.node.left, false));
}
}
}Note that the only thing that has changed is the order of pushing the children and the parent. Now we write the following code to test these out:
public static void main(String [] args){
BinaryTree<Integer> tree = new BinaryTree<>();
tree.addRoot(1);
Node<Integer> n1 = tree.getRoot();
Node<Integer> n2 = tree.addChild(n1, 2, true);
Node<Integer> n3 = tree.addChild(n1, 3, false);
Node<Integer> n4 = tree.addChild(n2, 4, true);
Node<Integer> n5 = tree.addChild(n2, 5, false);
Node<Integer> n6 = tree.addChild(n3, 6, true);
Node<Integer> n7 = tree.addChild(n3, 7, false);
Node<Integer> n8 = tree.addChild(n4, 8, true);
Node<Integer> n9 = tree.addChild(n4, 9, false);
Node<Integer> n10 = tree.addChild(n5, 10, true);
tree.traverseDepthFirst((x)->System.out.print(""+x), tree.getRoot(), DepthFirstTraversalType.PREORDER);
System.out.println();
tree.traverseDepthFirst((x)->System.out.print(""+x), tree.getRoot(), DepthFirstTraversalType.INORDER);
System.out.println();
tree.traverseDepthFirst((x)->System.out.print(""+x), tree.getRoot(), DepthFirstTraversalType.POSTORDER);
System.out.println();
System.out.println();
tree.traversePreOrderNonRecursive((x)->System.out.print(""+x));
System.out.println();
tree.traverseInOrderNonRecursive((x)->System.out.print(""+x));
System.out.println();
tree.traversePostOrderNonRecursive((x)->System.out.print(""+x));
System.out.println();
}We preserved the recursive versions as well so that we can compare the output, which is as follows:
1 2 4 8 9 5 10 3 6 7 8 4 9 2 10 5 1 6 3 7 8 9 4 10 5 2 6 7 3 1 1 2 4 8 9 5 10 3 6 7 8 4 9 2 10 5 1 6 3 7 8 9 4 10 5 2 6 7 3 1
The first three lines are the same as the last three, showing that they produce the same result.