CODEWITHSUNDEEP
pythonbinary-treetraversal
Sanya
Sanya

Reputation: 73

Binary Tree Level Order traversal - reversed

I am trying this coding problem on leetcode and not able to debug the error!!

It's been 3 hours and I tried re-writing the logic again but I am still missing something. What else can I add to make it work against the test case:

>>>input - [1,2,3,4,null,null,5]

>>>expected output - [[4,5],[2,3],[1]]

Although this code is working for the given test case:

>>> input - [3,9,20,null,null,15,7]

>>> output - [[15,7],[9,20],[3]]

This is my effort:

# 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]]:

        queue = []
        level = []

        result = []

        if root is None:
            return None

        result.append([root.val])
        queue.append(root)

        while len(queue) > 0:
            a = queue[0]

            ans = self.traverse_value(a.left, a.right, queue)

            if ans is not None:
                result.append(ans)

            queue.pop(0)

        return reversed(result)


    def traverse_value(self, r_left, r_right, queue):

        if r_left is None and r_right is None: # both l and r are none
            return
        elif r_left is None and r_right is not None: # right is not none
            queue.append(r_right)
            return [r_right.val]
        elif r_left is not None and r_right is None: # left is not none
            queue.append(r_left)
            return [r_left.val]
        elif r_left is not None and r_right is not None: # both are not none
            queue.append(r_left)
            queue.append(r_right)
            return [r_left.val, r_right.val]

Upvotes: 2

Views: 209

Answers (1)

trincot
trincot

Reputation: 350147

Your code can only create sublists of up to two elements, via the function traverse_value. This cannot be right, since obviously more wide trees will have more elements on the same level. Your algorithm has no provision to put "cousins" in the same list, only direct siblings.

Your BFS approach is certainly a good idea, but make sure to distinguish correctly between layers, so you know when to put values in the same list or in a new one:

    result = []
    if root is None:
        return None
    queue = [root]
    while len(queue):
        # get the values out of the current queue
        result.append([a.val for a in queue])
        # perform a separate loop for the this layer only
        nextlayer = []
        for a in queue:
            # just extend this new list for the whole layer
            if a.left:
                nextlayer.append(a.left)
            if a.right:
                nextlayer.append(a.right)
        # finally put that whole layer in the queue
        queue = nextlayer

    return reversed(result)

For your info, it can also be done with a DFS solution where you just keep track of the depth you are at, and use that as index in the solution list:

    level = []
    def recur(node, depth):
        if not node:
            return
        if depth >= len(level):
            level.append([])
        level[depth].append(node.val)
        recur(node.left, depth+1)
        recur(node.right, depth+1)

    recur(root, 0)
    level.reverse()
    return level

Upvotes: 1

Related Questions