Friedrich Ewald My Personal Website

Leetcode: Binary tree level order traversal

Given the root node of a binary tree, print all values in order, meaning from left to right on the same level. To solve this, we can use the standard breadth-first-search (BFS) algorithm in an iterative fashion with a queue. As an output we use a list and leverage the position -1 to add the current level to the list. For every level we append one new element to the end of the list.

from typing import List, Optional


# Definition for a binary tree node.
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


class Solution:
  def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
      return []
    
    res = []
    queue = [[root]]
    
    while len(queue) > 0:
      itms = queue[0]
      res.append([])
      queue.append([])
      for item in itms:
        res[-1].append(item.val)
        if item.left is not None:
          queue[-1].append(item.left)
        if item.right is not None:
          queue[-1].append(item.right)
      if len(queue[-1]) == 0:
        queue.pop()
      queue = queue[1:]

    return res


if __name__ == '__main__':
  s = Solution().levelOrder
  print(s(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))), [[3], [9,20], [15,7]])
  print(s(TreeNode(1)), [[1]])
  print(s(None), [])
Runtime: 74 ms, faster than 10.45% of Python3 online submissions for Binary Tree Level Order Traversal. Memory Usage: 14.2 MB, less than 84.74% of Python3 online submissions for Binary Tree Level Order Traversal.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.