Level order traversal of binary tree

Tags: , , ,

Level order traversal of a binary tree

Given a binary tree, print all the nodes of binary tree level-wise, this is another way of saying perform a breadth-first traversal of the binary tree and known as level order traversal of a binary tree. What is level order traversal of a binary tree? It means that nodes at a given level are printed before all the levels below it. For example, level order traversal of below tree would be [10,7,15,8,9,18,19]

Level order traversal of binary tree

Level order traversal: Thoughts

In a binary tree, each node has two children, when we process a node, we can already know what is at the next level. As the leftmost child at a given level has to be printed first, followed by its right sibling then by its cousins. If we store all the nodes at the next level from left to right, which data structure is best for this use case? It’s First In First Out pattern, hence the queue. Let’s see how it works with an example.

level order traversal of binary tree
level order traversal of binary tree

Start with root node and enqueue the root node in the queue.

breadth first traversal of binary tree
Root added to the queue

Now, while the queue is not empty,  dequeue node from the queue and push it’s left and right children onto queue if they exist. In this case, we will dequeue node(10) from the queue and enqueue node(7) and node(15) to queue. Output till now is 10.

level order traversal of binary tree
add next level to queue, output is 10.

Again, dequeue from the queue, node(7) and store it in output. At the same time, store it’s left child node(8) and right child node(9) to queue. The output is [10, 7]

Node(7) is dequeue and node(8) and node(9) enqueued

Now, dequeue node(15) from the queue, put it on to output and enqueue it’s left child node(18) and right child node(19) on to the queue. The output is [10,7,15].

Again, node(8) is dequeue from the queue and put on to the output, as there are no left and right child of node(8), nothing is enqueued in the queue. Same is true for all the nodes in the queue. We continue till queue is empty. Final output will be [10,7,15,8,9,,18,19].

Level order traversal of binary tree : implementation

    public ArrayList<Integer> levelOrderTraversal(TreeNode root){

        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> traversal = new ArrayList<>();

        if(root == null) return traversal;

        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode current = queue.poll();
            traversal.add((int)current.getValue());
		
            if(current.getLeft()!= null)
				queue.add(current.getLeft());
            if(current.getRight()!= null)
				queue.add(current.getRight());
        }
        return traversal;
    }

As each node of the binary tree is visited at least once, time complexity  O(n) along with space complexity of O(2(l-1)) where l is the number of levels in the binary tree.

The method explained above has an additional space complexity, is there a way to avoid that?  To print all the nodes on a particular level, first of all, we must know the number of levels in the binary tree, which is nothing but the height of the tree.

Start with level 0 and print all nodes on level 0, then move to level 1 and print all the nodes at level. To reach cousins of a node, we have to come back to the parent of the parent node of the current node. How about we always start at the root node with the desired level to be printed? If the node is at the desired level, print it and start again from the root.

Implementation wise it’s simple recursive function, where we pass the desired level to be printed, at each recursive call, the desired level decreases by 1. When the desired level is 1, print the node as that node will be at the level we are printing currently.

  • Find the height of the tree.
  • For each level:
    • Start from the root for each level.
    • Decrement the level count while moving to the left and right child.
    • If the level count is 1, print the node.
    • Else move down to left subtree and right subtree.

This algorithm is more useful when you have to print a specific level of binary tree and not all. Complexity of this method to do  level order traversal of binary tree is O(n log n). 

Level order traversal: recursive implementation

    public ArrayList<Integer>
	levelOrderTraversalRecursive(BinarySearchTree tree){
        ArrayList<Integer>traversal = new ArrayList<>();

        int height = tree.height();
        
        for(int i=1; i>=height; i++){
            traverseLevel(tree.getRoot(), i, traversal);
        }
        return traversal;
    }

    private void traverseLevel(TreeNode root, int level,
								ArrayList<Integer> levelTraversal){
        if(level == 1){
            levelTraversal.add((int) root.getValue());
        }

        if(root.getLeft() != null)
			traverseLevel(root.getLeft(), level-1, levelTraversal);
        if(root.getRight() != null)
			traverseLevel(root.getRight(), level-1,levelTraversal);
    }

Definition of binary tree and tree node is as follows.

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree<T> {

    private TreeNode<T> root;

    public void BinarySearchTree(){
        root = null;
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }
    private TreeNode insertNode(TreeNode root, int value){
        if(root == null){
            //if this node is root of tree
            root = new TreeNode(value);
        }
        else{
            if((int)root.getValue() > value){
             /* If root is greater than value, 
				node should be added to left subtree */
                root.setLeft(insertNode(root.getLeft(), value));
            }
            else{
                /* If root is less than value, 
				node should be added to right subtree */
                root.setRight(insertNode(root.getRight(), value));
            }
        }
        return root;
    }

    public TreeNode getRoot(){
        return this.root;
    }

    public void setRoot(TreeNode node){
        this.root = node;
    }

    public int height(){
        return height(this.getRoot());
    }

    private int height(TreeNode currentNode){
        if(currentNode == null) return 0;

        int lh = height(currentNode.getLeft());
        int rh = height(currentNode.getRight());

        return 1 + Integer.max(lh, rh);
    }
}
package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for a free session.