You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Depth First Traversal

Nicholas Wong
Nicholas Wong

There are 4 ways to do a depth first traversal, depends on how you would like to do it.

Define Node

static class Node {
    int value;
    Node left, right;
}

Depth First Recursive Traversal (Pre-order)

static boolean depthFirstTraversal_preOrder(Node node) {
    if (node == null) return true;
    if (!visit(node)) return false;
    if (!depthFirstTraversal_preOrder(node.left)) return false;
    if (!depthFirstTraversal_preOrder(node.right)) return false;
    return true;
}

Depth First Recursive Traversal (In-order)

static boolean depthFirstTraversal_inOrder(Node node) {
    if (node == null) return true;
    if (!depthFirstTraversal_inOrder(node.left)) return false;
    if (!visit(node)) return false;
    if (!depthFirstTraversal_inOrder(node.right)) return false;
    return true;
}

Depth First Recursive Traversal (Post-order)

static boolean depthFirstTraversal_postOrder(Node node) {
    if (node == null) return true;
    if (!depthFirstTraversal_postOrder(node.left)) return false;
    if (!depthFirstTraversal_postOrder(node.right)) return false;
    if (!visit(node)) return false;
    return true;
}

Depth First Iterative Traversal

static boolean depthFirstIterativeTraversal(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.empty()) {
        Node node = stack.pop();
        if (node == null) continue;
        if (!visit(node)) return false;
        stack.push(node.right);
        stack.push(node.left);
    }
    return true;
}

Full Example

import java.util.Stack;

/**
 * Created by nickwph on 10/18/15.
 */
public class BasicPractice_DepthFirstTraversal {

    static class Node {
        int value;
        Node left, right;

        Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static boolean visit(Node node) {
        return node.value == 1;
    }

    static boolean depthFirstTraversal_preOrder(Node node) {
        if (node == null) return true;
        if (!visit(node)) return false;
        if (!depthFirstTraversal_preOrder(node.left)) return false;
        if (!depthFirstTraversal_preOrder(node.right)) return false;
        return true;
    }

    static boolean depthFirstTraversal_inOrder(Node node) {
        if (node == null) return true;
        if (!depthFirstTraversal_inOrder(node.left)) return false;
        if (!visit(node)) return false;
        if (!depthFirstTraversal_inOrder(node.right)) return false;
        return true;
    }

    static boolean depthFirstTraversal_postOrder(Node node) {
        if (node == null) return true;
        if (!depthFirstTraversal_postOrder(node.left)) return false;
        if (!depthFirstTraversal_postOrder(node.right)) return false;
        if (!visit(node)) return false;
        return true;
    }

    static boolean depthFirstIterativeTraversal(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            Node node = stack.pop();
            if (node == null) continue;
            if (!visit(node)) return false;
            stack.push(node.right);
            stack.push(node.left);
        }
        return true;
    }

    static void verifyGoodTree() {
        Node node1 = new Node(1, null, null);
        Node node2 = new Node(1, null, null);
        Node node3 = new Node(1, null, null);
        Node node4 = new Node(1, node2, node3);
        Node node5 = new Node(1, node4, node1);
        Node node6 = new Node(1, null, null);
        Node node7 = new Node(1, null, null);
        Node node8 = new Node(1, node7, node6);
        Node node9 = new Node(1, node8, node5);
        System.out.println("Should be true: " + depthFirstTraversal_preOrder(node9));
        System.out.println("Should be true: " + depthFirstTraversal_inOrder(node9));
        System.out.println("Should be true: " + depthFirstTraversal_postOrder(node9));
        System.out.println("Should be true: " + depthFirstIterativeTraversal(node9));
    }

    static void verifyBadTree() {
        Node node1 = new Node(1, null, null);
        Node node2 = new Node(1, null, null);
        Node node3 = new Node(1, null, null);
        Node node4 = new Node(1, node2, node3);
        Node node5 = new Node(1, node4, node1);
        Node node6 = new Node(1, null, null);
        Node node7 = new Node(2, null, null);
        Node node8 = new Node(1, node7, node6);
        Node node9 = new Node(1, node8, node5);
        System.out.println("Should be false: " + depthFirstTraversal_preOrder(node9));
        System.out.println("Should be false: " + depthFirstTraversal_inOrder(node9));
        System.out.println("Should be false: " + depthFirstTraversal_postOrder(node9));
        System.out.println("Should be false: " + depthFirstIterativeTraversal(node9));
    }

    public static void main(String[] args) {
        verifyGoodTree();
        verifyBadTree();
    }
}
BasicPractice_DepthFirstTraversal.md
GitHub Gist: instantly share code, notes, and snippets.
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.