Level Order Traversal of Binary Tree - Recursive

In this tutorial, we will see the Level Order Traversal of a Binary Tree. This traversal is also known as BFS (breadth-first-search)traversal of a tree, because it visits the node from top of the tree and then goes down level by level. Now, let us have a look on a pictorial representation of Level Order Traversal.

The output of above shown tree would be: 2 5 10 20 30

Approach:

1. Firstly, we will find the height of the tree so that we can know how many levels are there to traverse.
2. Then we will start a loop from i to height of tree.
3. Then we will call a method levelOrder() which will print nodes level by level.

Algorithm for levelOrder()method:

public void levelOrder(Node node, int level, List<Integer> ls) {
if (node == null) return;
if (level == 0) add node.val into ls
else {
 call levelOrder(node.left, level - 1, ls);
 call levelOrder(node.right, level - 1, ls);
  }
}

Code Implementation:

• Java

import java.util.ArrayList;

import java.util.List;

public class LevelOrderTraversal {

    public static class Node {

        int val;

        Node left, right;

        // Constructor

        Node(int val) {

            this.val = val;

            left = right = null;

        }

    }

    public static void main(String[] args) {

        /*

         * Creating Binary Tree The created binary tree is same as in the above given

         * figure (refer figure for reference)

         */

        Node root = new Node(2);

        root.left = new Node(5);

        root.right = new Node(10);

        root.right.left = new Node(20);

        root.right.right = new Node(30);

        // this list of list will contain the final result

        List<List<Integer>> list = new ArrayList<>();

        // calculating height of tree

        int h = height(root);

        for (int i = 0; i < h; i++) {

            List<Integer> ls = new ArrayList<>();

            levelOrder(root, i, ls);

            list.add(new ArrayList<>(ls));

        }

        System.out.println(list);

    }

    private static void levelOrder(Node node, int level, List<Integer> ls) {

        if (node == null)

            return;

        if (level == 0) {

            ls.add(node.val);

        } else {

            levelOrder(node.left, level - 1, ls);

            levelOrder(node.right, level - 1, ls);

        }

    }

    public static int height(Node root) {

        if (root == null)

            return 0;

        int lh = height(root.left);

        int rh = height(root.right);

        return Math.max(lh, rh) + 1;

    }

}

Output:

[[2], [5, 10], [20, 30]]

Complexity Analysis:

Time Complexity: O(n²), In skewed tree the time worst case time complexity of recursive approach can go upto O(n²).
Space Complexity: In case of Skewed Tree O(n) and O(log n) if given tree is complete Binary Tree.