ProgramGuru.org

ProgramGuru.org

Level Order Traversal of a Binary Tree using Recursion

Visualization

Algorithm Steps

  1. Find the height of the binary tree.
  2. For each level from 1 to height, recursively traverse the tree to collect nodes at that level.
  3. The recursive function printLevel checks if the current level is 1; if so, it records the node's value, otherwise it recurses on the left and right children with level-1.
  4. Concatenate the nodes from each level to produce the level order traversal.

Level Order Traversal of a Binary Tree using Recursion - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

def printLevel(root, level, result):
    if not root:
        return
    if level == 1:
        result.append(root.val)
    elif level > 1:
        printLevel(root.left, level - 1, result)
        printLevel(root.right, level - 1, result)

def levelOrderTraversal(root):
    h = height(root)
    result = []
    for i in range(1, h + 1):
        printLevel(root, i, result)
    return result

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(levelOrderTraversal(root))