Tree Level Order Traversal

Understanding Tree Level Order Traversal

Tree Level Order Traversal is a method of visiting all the nodes in a tree level by level. It starts from the root node and proceeds to the next level, visiting all nodes at each level before moving to the next.

Implementation Using Queue

A common approach to implement level order traversal is by using a queue. Nodes are enqueued and dequeued as they are visited, ensuring that nodes at each level are processed in the correct order.

Example 1: Binary Tree Level Order Traversal

Consider the following binary tree:

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int item) {
        val = item;
        left = right = null;
    }
}

class BinaryTree {
    TreeNode root;

    void printLevelOrder() {
        Queue queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode tempNode = queue.poll();
            System.out.print(tempNode.val + " ");

            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }

            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }
    }
}
      

Example 2: N-ary Tree Level Order Traversal

For an N-ary tree, each node can have more than two children. The level order traversal can be adapted by enqueuing all children of a node before moving to the next node.

class NaryTreeNode {
    int val;
    List children;
    NaryTreeNode(int val) {
        this.val = val;
        children = new ArrayList<>();
    }
}

class NaryTree {
    NaryTreeNode root;

    void printLevelOrder() {
        Queue queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            NaryTreeNode node = queue.poll();
            System.out.print(node.val + " ");
            for (NaryTreeNode child : node.children) {
                queue.add(child);
            }
        }
    }
}
      

Example 3: Zigzag Level Order Traversal

Zigzag traversal alternates direction at each level, requiring a stack to reverse the order of nodes at every other level.

class ZigzagTraversal {
    List> zigzagLevelOrder(TreeNode root) {
        List> results = new ArrayList<>();
        if (root == null) return results;

        Queue queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val);
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            results.add(level);
            leftToRight = !leftToRight;
        }
        return results;
    }
}
      

Example 4: Level Order Traversal with Level Separation

This approach prints nodes level by level, separating each level's output for clarity.

class LevelOrderWithSeparation {
    void printLevelOrder(TreeNode root) {
        Queue queue = new LinkedList<>();
        queue.add(root);
        queue.add(null); // marker for end of level

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (node == null) {
                System.out.println(); // end of level
                if (!queue.isEmpty()) {
                    queue.add(null); // add marker for next level
                }
            } else {
                System.out.print(node.val + " ");
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
    }
}
      

Example 5: Recursive Level Order Traversal

Though less common, recursive methods can achieve level order traversal by maintaining a list of lists, where each index corresponds to a level.

class RecursiveTraversal {
    List> levels = new ArrayList<>();

    void helper(TreeNode node, int level) {
        if (levels.size() == level) levels.add(new ArrayList<>());

        levels.get(level).add(node.val);

        if (node.left != null) helper(node.left, level + 1);
        if (node.right != null) helper(node.right, level + 1);
    }

    List> levelOrder(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        return levels;
    }
}