---
tags: data_structure_python
---

# Binary Tree Level Order Traversal II <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

## Solution

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

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
    
        L, tmp = [], []
        queue = [root, None]
        
        while len(queue) > 0:
            node = queue.pop(0)
            
            if node != None:
                tmp.append(node.val)
                
                if node.left != None:
                    queue.append(node.left)
            
                if node.right != None:
                    queue.append(node.right)
            else:
                L.append(tmp)
                tmp = []
                if len(queue) > 0:
                    queue.append(None)
                
        return L[::-1]