Tut09 - james-bern/CS136 GitHub Wiki

image

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        
    XTree tree = new XTree();
    tree.root = new XNode(0);
    tree.root.children.add(new XNode(1));
    tree.root.children.add(new XNode(2));
    tree.root.children.add(new XNode(3));
    tree.root.children.get(0).children.add(new XNode(4));
    tree.root.children.get(0).children.add(new XNode(5));
    tree.root.children.get(0).children.get(0).children.add(new XNode(6));

    PRINT(tree.traverseBreadthFirst()); // [0 1 2 3 4 5 6]
    PRINT(tree.traversePreOrderDepthFirst()); // [0 1 4 6 5 2 3]
}
👀 Alternate Solution
public static void main(String[] arguments) {
    XTree tree; {
        XNode node0 = new XNode(0);
        XNode node1 = new XNode(1);
        XNode node2 = new XNode(2);
        XNode node3 = new XNode(3);
        XNode node4 = new XNode(4);
        XNode node5 = new XNode(5);
        XNode node6 = new XNode(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);

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

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

Implement traverseBreadthFirst

👀 Solution
ArrayList<XNode> traverseBreadthFirst() {
    ArrayList<XNode> result = new ArrayList<>();

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

    return result;
}

Implement traversePreOrderDepthFirst

👀 Solution
ArrayList<XNode> traversePreOrderDepthFirst() {
    ArrayList<XNode> result = new ArrayList<>();
    _traversePreOrderDepthFirstHelper(this.root, result);
    return result;
}

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

(Bonus) Implement traversePreOrderDepthFirst2 that doesn't use recursion ("bring you own stack")

Starter Code

import java.util.*;
class Tut09 extends Cow {
    
    static class XTree {
        XNode root;
        
        // HINT: A queue (ArrayDeque from Docs) will be helpful.
        ArrayList<XNode> traverseBreadthFirst() {
            ArrayList<XNode> result = new ArrayList<>();
            // TODO
            
            return result;
        }
        
        
        // HINT: Recursion will be helpful.
        ArrayList<XNode> traversePreOrderDepthFirst() {
            ArrayList<XNode> result = new ArrayList<>();
            _traversePreOrderDepthFirstHelper(root, result);
            return result;
        }
        
        void _traversePreOrderDepthFirstHelper(XNode curr, ArrayList<XNode> result) {
            // TODO
            
        }
    }
    
    static class XNode {
        int value;
        ArrayList<XNode> children;
        
        XNode(int value) {
            this.value = value;
            this.children = new ArrayList<>();
        }
        
        public String toString() {
            return "" + value;
        }
    }
    
    
    public static void main(String[] arguments) {
        //            0   
        //          / | \ 
        //         1  2  3
        //        / \     
        //       4   5    
        //       |        
        //       6        
        
        XTree tree = new XTree();
        XNode n0 = new XNode(0);
        tree.root = n0;
        // TODO: Set up tree to match the picture above.
        // NOTE: root.children should be [1, 2, 3] (same order left-to-right)
        
        
        PRINT(tree.traverseBreadthFirst()); // [0 1 2 3 4 5 6]
        PRINT(tree.traversePreOrderDepthFirst()); // [0 1 4 6 5 2 3]
    }
    
} 
⚠️ **GitHub.com Fallback** ⚠️