Tutorial 09

Implement breadth-first and (pre-order) depth-first traversal.

Create a simple test case in main

👀 Solution

public static void main(String[] arguments) {
    //            0   
    //          / | \ 
    //         1  2  3
    //        / \     
    //       4   5    
    //       |        
    //       6        
    Tree tree = new Tree();
    tree.root = new Node(0);
    tree.root.children.add(new Node(1));
    tree.root.children.add(new Node(2));
    tree.root.children.add(new Node(3));
    tree.root.children.get(0).children.add(new Node(4));
    tree.root.children.get(0).children.add(new Node(5));
    tree.root.children.get(0).children.get(0).children.add(new Node(6));

    System.out.println(tree.traverseBreadthFirst()); // [0 1 2 3 4 5 6]
    System.out.println(tree.traversePreOrderDepthFirst()); // [0 1 4 6 5 2 3]
}

👀 Alternate Solution

public static void main(String[] arguments) {
    Tree tree; {
        Node node0 = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node0.children.add(node1);
        node0.children.add(node2);
        node0.children.add(node3);
        node1.children.add(node4);
        node1.children.add(node5);
        node4.children.add(node6);

        Tree tree = new Tree();
        tree.root = node0;
    }

    System.out.println(tree.traverseBreadthFirst()); // [0 1 2 3 4 5 6]
    System.out.println(tree.traversePreOrderDepthFirst()); // [0 1 4 6 5 2 3]
}

Implement traverseBreadthFirst

👀 Solution

ArrayList<Node> traverseBreadthFirst() {
    ArrayList<Node> result = new ArrayList<>();

    ArrayDeque<Node> queue = new ArrayDeque<>();
    queue.add(root);
    while (queue.size() != 0) {
        Node curr = queue.remove();
        result.add(curr);
        for (Node child : curr.children) {
            queue.add(child);
        }
    }

    return result;
}

Implement traversePreOrderDepthFirst

👀 Solution

ArrayList<Node> traversePreOrderDepthFirst() {
    ArrayList<Node> result = new ArrayList<>();
    _traversePreOrderDepthFirstHelper(root, result);
    return result;
}

void _traversePreOrderDepthFirstHelper(Node curr, ArrayList<Node> result) {
    result.add(curr);
    for (Node child : curr.children) {
        _traversePreOrderDepthFirstHelper(child, result);
    }
}

Starter Code

import java.util.*;

class Tut09 {

    static class Node {
        int value;
        ArrayList<Node> children;

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

        public String toString() {
            return "" + value;
        }
    }

    static class Tree {
        Node root;


        // Gather the tree's nodes into an array list using a breadth-first traversal.
        // HINT: A queue (see Documentation) will be helpful.
        ArrayList<Node> traverseBreadthFirst() {
            ArrayList<Node> result = new ArrayList<>();
            // TODO

            return result;
        }


        // Gather the tree's nodes into an array list using a depth-first traversal.
        // NOTE: I assume you will use recursion.
        ArrayList<Node> traversePreOrderDepthFirst() {
            ArrayList<Node> result = new ArrayList<>();
            _traversePreOrderDepthFirstHelper(root, result);
            return result;
        }

        // Recursive helper function.
        void _traversePreOrderDepthFirstHelper(Node curr, ArrayList<Node> result) {
            // TODO

        }
    }

    public static void main(String[] arguments) {
        //            0   
        //          / | \ 
        //         1  2  3
        //        / \     
        //       4   5    
        //       |        
        //       6        

        Tree tree = new Tree();
        // TODO: Finish building the tree in the picture above.
        // NOTE: root.children should be [1, 2, 3]
        //       (same order as picture, reading left-to-right)

        System.out.println(tree.traverseBreadthFirst()); // [0 1 2 3 4 5 6]
        System.out.println(tree.traversePreOrderDepthFirst());   // [0 1 4 6 5 2 3]
    }

}