package DataStructures.Trees;⏎
⏎
import java.util.LinkedList;⏎
⏎
/**⏎
 * @author Varun Upadhyay (https://github.com/varunu28)⏎
 */⏎
⏎
⏎
// Driver Program⏎
public class TreeTraversal {⏎
    public static void main(String[] args) {⏎
        Node tree = new Node(5);⏎
        tree.insert(3);⏎
        tree.insert(2);⏎
        tree.insert(7);⏎
        tree.insert(4);⏎
        tree.insert(6);⏎
        tree.insert(8);⏎
⏎
        // Prints 5 3 2 4 7 6 8⏎
        System.out.println("Pre order traversal:");⏎
        tree.printPreOrder();⏎
        System.out.println();⏎
        // Prints 2 3 4 5 6 7 8⏎
        System.out.println("In order traversal:");⏎
        tree.printInOrder();⏎
        System.out.println();⏎
        // Prints 2 4 3 6 8 7 5⏎
        System.out.println("Post order traversal:");⏎
        tree.printPostOrder();⏎
        System.out.println();⏎
        // Prints 5 3 7 2 4 6 8⏎
        System.out.println("Level order traversal:");⏎
        tree.printLevelOrder();⏎
        System.out.println();⏎
    }⏎
}⏎
⏎
/**⏎
 * The Node class which initializes a Node of a tree⏎
 * Consists of all 4 traversal methods: printInOrder, printPostOrder， printPreOrder & printLevelOrder⏎
 * printInOrder: LEFT -> ROOT -> RIGHT⏎
 * printPreOrder: ROOT -> LEFT -> RIGHT⏎
 * printPostOrder: LEFT -> RIGHT -> ROOT⏎
 * printLevelOrder: Prints by level (starting at root), from left to right.⏎
 */⏎
class Node {⏎
    Node left, right;⏎
    int data;⏎
⏎
    public Node(int data) {⏎
        this.data = data;⏎
    }⏎
⏎
    public void insert(int value) {⏎
        if (value < data) {⏎
            if (left == null) {⏎
                left = new Node(value);⏎
            } else {⏎
                left.insert(value);⏎
            }⏎
        } else {⏎
            if (right == null) {⏎
                right = new Node(value);⏎
            } else {⏎
                right.insert(value);⏎
            }⏎
        }⏎
    }⏎
⏎
    public void printInOrder() {⏎
        if (left != null) {⏎
            left.printInOrder();⏎
        }⏎
        System.out.print(data + " ");⏎
        if (right != null) {⏎
            right.printInOrder();⏎
        }⏎
    }⏎
⏎
    public void printPreOrder() {⏎
        System.out.print(data + " ");⏎
        if (left != null) {⏎
            left.printPreOrder();⏎
        }⏎
        if (right != null) {⏎
            right.printPreOrder();⏎
        }⏎
    }⏎
⏎
    public void printPostOrder() {⏎
        if (left != null) {⏎
            left.printPostOrder();⏎
        }⏎
        if (right != null) {⏎
            right.printPostOrder();⏎
        }⏎
        System.out.print(data + " ");⏎
    }⏎
⏎
    /**⏎
     * O(n) time algorithm.⏎
     * Uses O(n) space to store nodes in a queue to aid in traversal.⏎
     */⏎
    public void printLevelOrder() {⏎
        LinkedList<Node> queue = new LinkedList<>();⏎
        queue.add(this);⏎
        while (queue.size() > 0) {⏎
            Node head = queue.remove();⏎
            System.out.print(head.data + " ");⏎
            // Add children of recently-printed node to queue, if they exist.⏎
            if (head.left != null) {⏎
                queue.add(head.left);⏎
            }⏎
            if (head.right != null) {⏎
                queue.add(head.right);⏎
            }⏎
        }⏎
    }⏎
}⏎