Tree Traversal Techniques

There are mainly two ways in which we can traverse a tree:
1. Breadth-First (or) Level Order Tree Traversal
2. Depth-First Tree Traversal

Breadth-First/Level Order Tree Traversal:
Here we traverse/print all the nodes available at an order, before going to next order
We go from top to bottom
                            1
             2                              3
   4               5           6                      7

For this tree, the Level Order Traversal is: 1, 2, 3, 4, 5, 6, 7

Algorithm:
a. Initialize a queue
b. enQueue root on to queue.

c. while queue is not empty
    deQueue the queue and print its contents
    push deQueue'd node's left and right nodes into queue

class LevelOrderTrav {
        static public void levelOrderTrav(TreeNode root) {
                if(root == null) {
                        System.err.println("Tree is empty...");

                        return;
                }

                ListQueue q = new ListQueue();
                q.enQueue(root);

                while(! q.isEmpty()) {
                        TreeNode node = q.deQueue();

                        System.out.print(node.getData() + ", ");

                        if(node.getLeft() != null)
                                q.enQueue(node.getLeft());

                        if(node.getRight() != null)
                                q.enQueue(node.getRight());
                }

                System.out.println();
        }

        static public void main(String[] args) {
                levelOrderTrav(TreeUtil.getTree());
        }
}

Depth-First Traversing Techniques:

These are again divided into 3 types, based on when the data(D) is printed.

1. PreOrder (DLR): Print Data, Traverse Left Tree and then Traverse Right Tree

2. InOrder(LDR): Traverse Left Tree, Print Data and then Traverse Right Tree

3. PostOrder(LRD): Traverse Left Tree, Traverse Right Tree and then Print data

Recursive way of traversing tree:

class RecTraversal {
        //DLR
        static public void recPreOrder(TreeNode node) {
                if(node != null) {
                        System.out.print(node.getData() + ", ");

                        recPreOrder(node.getLeft());
                        recPreOrder(node.getRight());
                }
        }

        //LDR
        static public void recInOrder(TreeNode node) {
                if(node != null) {
                        recInOrder(node.getLeft());
                        System.out.print(node.getData() + ", ");
                        recInOrder(node.getRight());
                }
        }

        //LRD
        static public void recPostOrder(TreeNode node) {
                if(node != null) {
                        recPostOrder(node.getLeft());
                        recPostOrder(node.getRight());
                        System.out.print(node.getData() + ", ");
                }
        }

        static public void main(String[] args) {
                TreeNode node = TreeUtil.getTree();

                recPreOrder(node);
                System.out.println();

                recInOrder(node);
                System.out.println();

                recPostOrder(node);
                System.out.println();
        }
}
~