GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Tree Traversal

Date: May 17, 2016
import java.util.LinkedList;
import java.util.List;
import java.util.Iterator;
import java.util.Queue;


public class TreeTraversal {

    public static void main(String[] args) {

        Node head = new Node(0);
        makeTree(head, 15);

        depthFS(head);
        System.out.println();
        breadthFS(head);
    }

    public static void depthFS(Node curNode) {

        if (curNode == null) {
            return;
        }

        visit(curNode);
        Iterator<Node> iter = curNode.getChildren().iterator();

        while (iter.hasNext()) {
            depthFS(iter.next());
        }
    }

    public static void breadthFS(Node head) {

        if (head == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);

        while (!queue.isEmpty()) {

            Node curNode = queue.remove();
            visit(curNode);

            List<Node> children = curNode.getChildren();
            Iterator<Node> iter = children.iterator();

            while (iter.hasNext()) {
                queue.add(iter.next());
            }
        }
    }

    public static void visit(Node n) {
        System.out.println(n.value);
    }

    public static void makeTree(Node head, int numNodes) {

        LinkedList<Node> parentQueue = new LinkedList<Node>();
        parentQueue.add(head);
        Node curParent = null;

        for (int i = 0; i < numNodes; i += 2) {

            curParent = parentQueue.remove();

            Node leftChild = new Node(i + 1);
            Node rightChild = new Node(i + 2);

            curParent.getChildren().add(leftChild);
            curParent.getChildren().add(rightChild);

            parentQueue.add(leftChild);
            parentQueue.add(rightChild);
        }
    }

    public static class Node {

        int value;
        List<Node> children;

        public Node(int value) {
            this.value = value;
            children = new LinkedList<Node>();
        }

        public void addChild(Node child) {
            children.add(child);
        }

        public List<Node> getChildren() {
            return children;
        }
    }
}