Algorithm {Binary Tree Level Order Traversal II}

Hi,

Today we will work on the tree traversal task – Binary Tree Level Order Traversal II. We can see that task is pointed as second (II) it means not simple/classic level order traversal, so, let’s read task description:

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

So, as expected task is not usual classic traversal, we should print tree from bottom to top.

Stop and think what do we have and what we should to do.

We have classic binary tree. And we should traverse this tree level by level and after that create result list from end level to first. So, during traversing we can store level by level data until last and after that read from top level by level and put to result list. What data structure has that behaviour? Yes, Stack (LIFO).

So, we have analysed problem let’s implement it:

That is all, and leetcode accepted solution :)

Thanks!

Algorithm {Linked List Cycle/II}

Hi, Today we will learn how to solve two problems from leetcode – Linked List Cycle and Linked List Cycle II. So, as you can see these problems are related but first easiest and second more complex. OK, first task description:

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

So, it’s easy if you know Robert W. Floyd algorithm also called “tortoise and the hare” algorithm. Full description you can read in wiki. I am going to provide short description before implementation. Main idea of algorithm is two pointers. First one slow or tortoise, second one is fast or hare. Slow pointer will be moved node by node, fast one node after node i.e. twice faster than slow one. So, when slow pointer run through distance x fast 2x and if there is loop fast will catch up slow, this is rule to stop loop.

OK, try to implement it:

you can see that is very easy to develop and understand. OK, let’s move to the second task:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

This task is more complex, because you should find start cycle node. But if you again read tortoise and the hare algorithm you should understand this is not so hard.

Short transcript of the wiki description:

When fast caught slow, slow is stay in the same distance to first cycle node as from start to first cycle node. So, if we start new one pointer from start (or move slow or fast to start) and run node by node we will get first cycle node. Super!

Lets implement it:

Perfect, both solutions were accepted by leetcode.

Cheers!