Iterate over Binary Search Tree (BST) - DepthFirst (preOrder, inOrder, postOrder ) , breadthFirst (Java Code)

Problem :

Traverse over binary search  tree.

Solution -

Lets take very simple tree with 2 as root and left as 1 and right as 2.

Depth First : Traverse through columns/vertical . For very big binary search tree such traversal could be time consuming .
Goes to farthest left node then traverse remaining and then go to farthest right node .

Pre-Order traversal  = 2,1,3
In-Order traversal =  1,2,3 (it is always sorted list in ascending order.)
Post-Order traversal = 1,3,2

Same logic will apply for any BST with any number of nodes .

Typically these are recursive functions otherwise stack is used to implement non-recursive functions.
It will be same logic for binary tree and graph .

Breath First :

Typically it is implemented using  queue .

Traverse through rows/horizontal  . For very big binary tree optimization could  be done like after 100th level ignore next levels etc .
Traverse one level distance away in each recursion .
It will be same logic for binary tree and graph .

level by level traversal = 2,1,3 or 2,3,1

Same logic will apply for any BST with any number of nodes .

package com.salpe.tree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.logging.Logger;

import org.junit.Test;

import com.salpe.tree.BSTUtils.BST.IteratorType;

/**
 * Binary tree could be traversed in two ways 
 * 1. Depth First
 *   a) pre-order
 *   b) in-order
 *   c) post-order
 * <p>
 * 2. Breadth First - level by level
 * </p>
 *
 */

public class BSTUtils {

 // logger 
 private static final Logger s_logger = Logger.getLogger(BSTUtils.class.getName());

 // Binary tree node model 
 static class BST<T extends Comparable<T>> {

  public enum IteratorType {

   PRE_ORDER, IN_ORDER, POST_ORDER,

   BREATH_FIRST;
  }

  private BSTNode<T> root;

  private int length;

  public void add(T data) {

   if (root == null) {

    root = new BSTNode<T>(data, null, null);
   } else {

    add0(root, data);

   }

  }

  /**
   * BST shape depends on order of insertion - not optimized for re-balancing 
   * @param node
   * @param data
   * @return added node
   */
  private BSTNode<T> add0(BSTNode<T> node, T data) {

   if (node == null) {

    length++;
    return new BSTNode<T>(data, null, null);
   }

   if (data.compareTo(node.id) < 0) {

    node.left = add0(node.left, data);

   } else if (data.compareTo(node.id) > 0) {

    node.right = add0(node.right, data);
   } else {

    return node;
   }

   return node;
  }

  /**
   * For searching binary tree must be binary search tree.
   * 
   * @param data
   * @return searched node
   */
  public BSTNode<T> search(T data) {

   BSTNode<T> start = root;

   while (start != null) {
    if (data.compareTo(start.id) < 0) {
     start = start.left;
    } else if (data.compareTo(start.id) > 0) {
     start = start.right;
    } else {
     return start;
    }
   }

   return null;
  }

  /**
   *  Iterator design pattern .
   *  But it is eager fetching so not true iterator design pattern 
   *  
   * @param type
   * @return Iterator
   */
  public Iterator<T> iterator(IteratorType type) {
   LinkedList<T> list = new LinkedList<>();
   switch (type) {
   case PRE_ORDER:
    preOrderTraversal(root, list);
    break;
   case IN_ORDER:
    inOrderTraversal(root, list);
    break;
   case POST_ORDER:
    postOrderTraversal(root, list);
    break;
   case BREATH_FIRST:
    breadthFirstTraveral(root, list);

   default:
    break;
   }

   return list.iterator();

  }

  /**
   * first visit left then current then right node.
   *  Could be converted in non-recursive function using stack 
   * @param node
   * @param list
   */
  private void inOrderTraversal(BSTNode<T> node, LinkedList<T> list) {

   if (node == null) {

    return;
   }

   inOrderTraversal(node.left, list);
   list.add(node.id);
   inOrderTraversal(node.right, list);
  }

  /**
   * first visit current then left and then right node.
   * Could be converted in non-recursive function using stack 
   * @param node
   * @param list
   */
  private void preOrderTraversal(BSTNode<T> node, LinkedList<T> list) {

   if (node == null) {

    return;
   }

   list.add(node.id);
   preOrderTraversal(node.left, list);
   preOrderTraversal(node.right, list);
  }

  /**
   * first visit left then current and then right node
   * Could be converted in non-recursive function using stack 
   * @param node
   * @param list
   */
  private void postOrderTraversal(BSTNode<T> node, LinkedList<T> list) {

   if (node == null) {

    return;
   }

   postOrderTraversal(node.left, list);
   postOrderTraversal(node.right, list);
   list.add(node.id);
  }

  /**
   * Level by level traversal using queue
   * 
   * @param node
   * @param list
   */
  private void breadthFirstTraveral(BSTNode<T> node, LinkedList<T> list) {

   LinkedList<BSTNode<T>> queue = new LinkedList<>();

   queue.offer(node);

   while (queue.size() != 0) {

    BSTNode<T> nodeToVisit = queue.poll();

    list.add(nodeToVisit.id);

    if (nodeToVisit.left != null)
     queue.offer(nodeToVisit.left);
    if (nodeToVisit.right != null)
     queue.offer(nodeToVisit.right);
   }

  }

 }

 /**
  * Binary tree model can used as BST also
  * 
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  private T id;

  private BSTNode<T> left;

  private BSTNode<T> right;

  public BSTNode(T id, BSTNode<T> left, BSTNode<T> right) {
   super();
   this.id = id;
   this.left = left;
   this.right = right;
  }

  @Override
  public String toString() {
   return "BSTNode [id=" + id + "]";
  }

 }

 @Test
 public void test() {

  // create empty BST
  BST<Integer> bst = new BST<>();

  // add nodes
  bst.add(4);

  bst.add(2);
  bst.add(5);

  bst.add(1);
  bst.add(3);

  bst.add(6);
  bst.add(7);

  // binary search tree in-order representation is 1,2,3,4,5,6,7 where
  // root is 4

  print(IteratorType.PRE_ORDER, bst.iterator(IteratorType.PRE_ORDER));

  print(IteratorType.IN_ORDER, bst.iterator(IteratorType.IN_ORDER));

  print(IteratorType.POST_ORDER, bst.iterator(IteratorType.POST_ORDER));

  print(IteratorType.BREATH_FIRST, bst.iterator(IteratorType.BREATH_FIRST));

 }

 private static void print(IteratorType type, Iterator<Integer> itr) {

  StringBuilder bld = new StringBuilder(type.name()).append(" ---> ");

  while (itr.hasNext()) {

   bld.append(itr.next()).append(" ,");
   
  }

  s_logger.info(bld.toString());

 }

}