• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

Level Order Traversal in Binary Tree | Explained with Code and Example

Aniruddha Chaudhari/8958/0
CodeCSE SubjectData StructurePython

Traversal is an algorithm for visiting each node in a different fashion. Earlier we have seen see pre-order, in-order and post-order BT traversal.

Now we are interested in level order traversal.

What is level order traversal in Binary Tree?

In level order traversal, we visit (print) nodes of the binary tree at level zero, then at level one, two and so on…

reorder, inorder and post order traversal

For the above binary tree, the level order traversal is 4, 1, 5, 7, 3, 6.

  • The node at level one is 4.
  • The node at level two is 1 and 5.
  • The node at level three is 7, 3, 6.

Note: The number of levels in the binary tree is one more than the height of the tree (or root node). In the above example, the height of the BT is two and the total number of levels is three (2+1).

Algorithm

1. Find the height of the binary tree
2. Repeat for each level (1 to height+1)
- Print the value of nodes at that level. 
  (Use recursion here to print the values.)

To implement level order traversal, it is required to find the height of a Binary Tree.

Python Program

Here is a simple Python program for level order traversal using recursion.

class node:
    def __init__(self, val, left=None, right=None):
        self.left=left
        self.val=val
        self.right=right

def height(root):
    if root:
        return 1+max(height(root.left), height(root.right))
    else:
        return -1

def printAtLevel(root, level):
    if root:
        if level==1:
            print(root.val)
        else:
            printAtLevel(root.left, level-1)
            printAtLevel(root.right, level-1)
    
def levelOrderTraversal(root):
    for i in range(1,height(root)+2):
        printAtLevel(root, i)
        

root=node(4)
root.left=node(1)
root.right=node(5)
root.left.left=node(7)
root.left.right=node(3)
root.right.right=node(6)
levelOrderTraversal(root)

Output:

4
1
5
7
3
6
8

If Python is not your primary language, try to solve this problem in C/C++, Java or any programming language you are comfortable with. You can use the same algorithm and logic.

Complexity

The worst-case complexity of the algorithm is with a skewed binary tree where each node will be having either one or two nodes.

In the skewed tree, to print the element at level one (function printAtLevel()) take the time of O(1), to print the element at level two takes the time of O(2)… to print the element at level n takes the time of O(n)…

(Where, n is the number of nodes in the binary tree.)

To print all the elements at each level is O(1)+O(2)+O(3)+…+O(n)=O(n^2).

So, in the worst case, the time complexity of level order traversal in binary tree is O(n^2).

algorithmBinary Tree
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Leave a Reply Cancel reply

Binary Tree (BT)

  1. BT- Introduction
  2. BT- Create Binary Tree
  3. BT- Pre/In/Post Order Traversal
  4. BT- Height 
  5. BT- Level Order Traversal
  6. BT- Min and Max Heap
  7. BT- Parent of a Given Node
  8. BT- Ancestors of Given Node
  9. BT- Lowest Common Ancestor
  10. BT- Check Sub Tree

Binary Search Tree (BST)

  1. BST- Introduction
  2. BST- Search Node
  3. BST- Insert Node

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard