Saturday, October 12, 2019

Leetcode solution 103: Binary Tree Zigzag Level Order Traversal

Problem Statement 

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

It’s purely an implementation problem to be honest. Very similar to to binary tree level order traversal, we just need to use some data structure to hold the values while we control the traversal order. I choose to use a deque (i.e., doubled linked list) to keep the order. You can also use a queue like many other online solutions but note when calling add(0, value) to an array list is not very efficient since to have array copy every time.

Solutions


Time Complexity: O(N) since we visit each node once
Space Complexity: O(N) since used a deque

References

Saturday, October 5, 2019

Leetcode solution 199: Binary Tree Right Side View

Problem Statement 


Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is a great problem and I highly recommend we solve it in both DFS and BFS for level order traversal because it  covers everything we need to know about trees in interviews.

This would be a better test case because right subtree would not be deep enough to cover the left subtree
   1            <---
 /   \
2     3         <---
 \     
  5             <---
[1, 3, 5] 

Level order traversal using BFS(queue)

It should be relatively natural for us think about using level order traversal and we can simply use a queue and always find the right most element when we pop out element from each level.

Level order traversal using DFS(map)

A pre-order traversal way, just like order level traversal using DFS with a map(key is depth, value is node). This method utilizes a depth to value map to record the right most value on each order while performing a pre-order traversal, namely record the node value, go left then go right. This way, right value can always overwrite the left value thus keeping a “right side view”



I personally don't like the leetcode official solution, where in DFS you don’t need two stacks and in
BFS you don’t need the maps.

Follow up, how about implement a left side view? Trivial right?

Solutions

Level order traversal using BFS(queue)


Time Complexity: O(N) since we visit each node once
Space Complexity: O(N), more precisely the number of element on the last level, aka queue size when it’s a complete tree


Level order traversal using DFS(map)

Time Complexity: O(N) since we visit each node once

Space Complexity: O(lgN) because we are using a map and map size should be tree height, which worst case could be O(N)

References