Path in ZigZag Labelled Binary Tree

Every so often when I am practicing algorithm problems, I run into a problem that requires a bit of math to solve. For this “Path in ZigZag Labelled Binary Tree” problem, my initial impression was that I would have to do a breadth-first search on a tree. As I quickly found out, I was not dealing with a typical tree problem. This problem requires a bit of math to solve. I don’t know about you, but my math is a bit rusty.

The Problem

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example

Example 1:
Input: label = 14
Output: [1, 3, 4, 14]

Example 2:
Input: label = 26
Output: [1, 2, 6, 10, 26]

Link to Problem

Some Math

As promised there is going to be some math. I just want to go over some concepts to make sure that we are on the same page.

First off, here is a post about tree basics. In this problem we are dealing with a full and complete binary tree. This is also known as a perfect binary tree. For a perfect binary tree, each level has exactly twice as many nodes as the previous level.

Let’s refresh our memories on logarithms a bit. I found two great resources to help us do that. Here is one by VC that is pretty good and here is one by Vaidehi Joshi that is pretty good as well. I like some things that VC says:

Log of a number is the number of times you need to divide that number by the ‘base’ to get an output equal to 1.”

I like how VC explains it in terms that us simple folk can understand. Let’s look at some examples.

log2(8) = 3. Divide 8 by 2 (the base). Do it 3 times and you get 1.
Log10(10000) = 4. Divide 10000 by 10 (the base). Do it 4 times and you get 1.

Ok, so that’s not so bad. Now let’s see how this can be applied to the perfect binary tree in the problem. First take a look at the figure below to see how we are going to refer to the depths of of the levels for the binary tree in this problem.

For starters, let’s see how we can find both the fist and last node in a level for a particular depth.

Let’s see how this can be applied to depth = 3.

Here is a neat trick. Let’s see if we can find how many nodes are contained up until a certain depth.

Now let’s see how for a particular node number, we are able to find the depth that the node is located.

The example for finding the depth from a node number uses numbers that have 2 as a root. Let’s look at when this isn’t the case.

log2(10) = 3.32 ~ 3
log2(13) = 3.70 ~ 3

As you can see, although node 10 and node 13 come out to decimal, they still have a depth of 3. So, when we are finding depth based off a node number, we will floor the result.

Well, I think we have just about the covered the basics. Let’s start figuring out how to solve the problem.

Brute Force

This problem is essentially asking us to return a list that has the path from a node to the root.

When I tried to solve the problem, I first built a tree that contained nodes for all the values up until the “label” that is given as input. I didn’t actually build a tree though. I instead used nested lists to represent each level of the tree. The lists followed the zigzag pattern.

What I realized is that if you take the node that corresponds to the label given as input then you can can assign an index value to that node. Then take that index value and divide by two. This will give the index value of the parent node. In the example below, I used label = 10 to make it more interesting.

Something to note is that if the tree was not in a zigzag pattern and was a “normal tree”, then the node values could be divided by two to get the value of the parent node. Go up to the “Normal Tree” picture above and try it. Just make sure to floor the result.

Here is the code for the brute force approach that I took:

Pretty good approach in my opinion. Just not quite fast enough for the big leagues. The time complexity of this algorithm is O(n + logn) with n = label. The space complexity is O(n + logn) as well.

Optimal Solution

Here is some real top-notch code submitted by LeetCode user @alok5. You can find the original post here.

The basic idea behind the algorithm is fairly straightforward.

Add the node to the back of the result list.
Find the depth of the node.
Find the parent of the node.
Repeat steps with the parent as the new node.

When using Math.log() in Java, it defaults to base 10. In the algorithm Math.log(parent) / Math.log(2) is how to change the base to two. Read more about that here.

Some Illustrations

Let’s take a look at some illustrations to really give us a crystal clear mental picture of what is happening with this algorithm.

Ok, so I know what you are thinking. This tree does not follow the zigzag pattern that is described in the problem. In fact it is a pretty normal-looking full and complete binary tree with the exception of the last level. The last level is reversed.

That’s right. Only the last level is reversed. This is the level that contains the “label”. Label or the “parent” is shaded red. The other nodes in this level are shaded blue. This blue-shaded level is the only level that is reversed.

Why is only this level reversed?

Go back up to the “Normal Tree” picture. The parent of the node 14 is 7. However, in the zigzag tree the parent of node 14 is 4. To find the parent in the zigzag tree, think of it like this.

Pretend we are actually dealing with a normal tree. To find the “zigzag” parent in a normal tree we can do one of two things:

We can reverse the current level. Now the parent of the node in the reversed level is the desired “zigzag parent”.
We can reverse the level above. Now the parent of the label node is the desired “zigzag parent”.

That is what offset is doing. If you remember from above, 2^(depth + 1) – 1 is the last node for a particular level. Last node – parent = distance that parent is from end of the level = offset.

Remember that the first node = 2^(depth). So then take the offset value (1) and add it to the first node in the level (8) and divide this value by 2.
(8 + 1) / 2 = 9 / 2 = 4. In a normal tree, the parent of node 9 is 4.

So really we are finding the parent of node 9 in a normal tree. Node 9 is like the mirror node for 14. Offset is like finding the mirror value for a node.

The same thing happens when parent = 4. The offset is 3. So 7 is like the mirror value for 4. So, when this level gets reversed, 4 goes in the place where 7 was. 3 is the “zigzag parent” of 4.

Same thing happens again, but there is only the root node left, so it doesn’t matter so much. Also notice that parent = 1. This terminates the while loop and the result is returned

result = [1, 3, 4, 14]

Time Complexity

The time complexity for this algorithm is O(logn) with n = label.

Space Complexity

The space complexity of this algorithm is O(logn) as well.

Learn some more Big-O tips and tricks.

Get Better at Algorithms!

Algorithms and data structures are pretty tough. They are definitely taking a while for me to get the hang of them. However, there are some great resources out there, and I feel obligated to share some that have been most helpful to me. If I missed any that have been helpful to you, be sure to mention them in the comments.

Cracking the Coding Interview – Great resource. Really gets you in the right mindset for interviews. You can find it here.
Elements of Programming Interviews – Another great book. Personally, I like this one more than CTCI, but YMMV. You can find it here.
Grokking the Coding Interview – Can’t emphasize this one enough. Haven’t seen it mentioned it too often. Explains patterns that occur in different coding challenge problems. Great at providing a big-picture of all the different algorithm problems you might encounter. Check it out here.
Grokking Dynamic Programming – Dynamic programming is tough. This course has definitely helped me get a better understanding.
Tushar Roy – Tushar really knows his stuff. His dynamic programming playlist is especially good. Check out his awesome YouTube channel.
Back To Back SWE – Great YouTube Channel. Highly recommend.
Kevin Naughton Jr. – Another awesome YouTube channel. Great at going over problems and gives helpful advice.
Base CS – Vaidehi Joshi does a great job of laying out the fundamentals of algorithms and data structures. Check out the blog series here. She also has a podcast that I give two thumbs up.
Coding Challenge Website – There are plenty of different ones to choose from. HackerRank, CodeWars, and Edabit all seem to be pretty popular. I personally use LeetCode. Find the one that works for you!
Pramp – Do mock interviews! The sooner the better! Pramp has been a huge help to me.

Well, I hope that was useful. Thanks for reading my post and best of luck with your learning about data structures and algorithms!