CODEWITHSUNDEEP
pythonbinary-treebinary-search-tree
Faisal Khan
Faisal Khan

Reputation: 113

Python Leetcode BST: Level Order Traversal

I am trying to solve the Leetcode problem: 102. Binary Tree Level Order Traversal and hit a snag. My code below does not give the correct output and I have been trying to figure out what is the issue since it is not appending the last level in the tree. I would appreciate it someone can assist in making this code work.

# 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]]:
        while not root:
            return []

        queue = [root]
        result = [[queue[0].val]]

        while queue:
            nodes = queue
            level_nodes = []
            temp = []
            for node in nodes:
                level = queue.pop(0)
                if node.left:
                    level_nodes.append(level.left.val)
                    temp.append(node.left)
                if node.right:
                    level_nodes.append(level.right.val)
                    temp.append(node.right)
            queue = temp
            result.append(level_nodes)
        return result

Input: root = [3,9,20,null,null,15,7]

Expected Output: [[3],[9,20],[15,7]]

Output I am getting: [[3],[9,20],[]]

Reference: https://leetcode.com/problems/binary-tree-level-order-traversal/description/

Upvotes: 0

Views: 209

Answers (1)

Faisal Khan
Faisal Khan

Reputation: 113

I have been able to solve the problem and leave it for reference anyone who is doing it in this way (Not trying to use deque from collisions library). This solution was accepted by LeetCode.

# 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]]:
        while not root:
            return []

        queue = [root]
        result = []

        while queue:
            level_nodes = []
            temp = []
            for node in queue:
                level_nodes.append(node.val)
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.a bppend(node.right)
            queue = temp
            result.append(level_nodes)
        return result

Upvotes: 1

Related Questions