Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Reverse Level Order Traversal

Problem Statement

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., the lowest level comes first in left to right order.)

Examples

Example 1

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
  • Expected Output: [[4, 5, 6, 7], [2, 3], [1]]
  • Justification:
    • The third level has 4, 5, 6, and 7 nodes.
    • The second level has 2 and 3 nodes.
    • The first level has a single node with the value 1.

Example 2

  • Input: root = [12, 7, 1, null, 9, 10, 5]
  • Expected Output: [[

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Sheraz Khan

· 4 years ago

Instead of appending list at the beginning to reverse, why not use Stack instead?

Show 2 replies
M

madhu.sambangi

· 3 years ago

Instead of LinkedList to hold the level arrays and adding at the beginning of the LinkedList every time, a Stack<List<Integer>> is another option we could try. It worked for me.

G

greenwald.juj

· 3 years ago

This is a little confusing since you expect that what's in the boiler plate here is suppose to be in the solution

Boiler Plate for Question

class Solution:
  def traverse(self, root):
    deq = deque()
    # TODO: Write your code here

    result = [list(sublist) for sublist in deq]
    return result

Solution - FOLLOWS SIMILAR FORMAT AS 'LEVEL ORDER TRAVERSAL' QUESTION

def traverse(root):
  result = deque()
  if root is None:
    return result

  queue = deque()
  queue.append(root)
  while queue:
    levelSize = len(queue)
    currentLevel = []
    for _ in range(levelSize):
      currentNode = queue.popleft()
      # add the node to the current level
      currentLevel.append(currentNode.val)
      # insert the children of current node in the que
Semih kekül

Semih kekül

· 3 years ago

In the problem function returns vector<vector<int>> In the solution it returns deque<vector<int>> This is a huge difference. Please update!

S

Shlomi Fisher

· 2 years ago

instead of:

result.push_back(currentLevel);

use:

result.insert(result.begin(), currentLevel);

It's a simple change that works. it might incur more moves in the container though.

R

ryan

· 2 years ago

Reverse Level Order Traversal Testcases seems wrong. My code unchanged from Level Order Traversal works.

Show 1 reply
Kim Dean

Kim Dean

· 2 months ago

The time complexity actually seems to be quadratic (O(N^2)) because array.unshift (reversing)takes linear time inside the loop. As others have suggested, using a stack to store the levels and then reversing them at the end would optimize this to true linear time.