Interview Practice Basic – Breathe First Traversal

In the iterative way

You can only do breathe first traversal in iterative way. Though you can still make it recursive by calling itself in each loop, but you will not benefit from it. It is similar to doing depth first traversal, instead you use a FIFO queue to store the nodes.

Node definition

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

Breathe first iterative traversal

static boolean breatheFirstIterativeTraversal(Node root) {
    Queue<Node> stack = new LinkedList<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        Node node = stack.poll();
        if (node == null) continue;
        if (!visit(node)) return false;
        stack.add(node.left);
        stack.add(node.right);
    }
    return true;
}

Full example

import java.util.LinkedList;
import java.util.Queue;

public class BasicPractice_BreatheFirstTraversal {

    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 breatheFirstIterativeTraversal(Node root) {
        Queue<Node> stack = new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.poll();
            if (node == null) continue;
            if (!visit(node)) return false;
            stack.add(node.left);
            stack.add(node.right);
        }
        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: " + breatheFirstIterativeTraversal(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: " + breatheFirstIterativeTraversal(node9));
    }

    public static void main(String[] args) {
        verifyGoodTree();
        verifyBadTree();
    }
}

Leave a Reply

%d bloggers like this: