Write a method to find the zig zag tree traversal in a tree. I got asked this question once in an interview. Now I found a few solutions to this problem over the internet, but none was really explaining how to get to the solution, instead just provide one. I will try to explain step by step how to come up with a solution, so you get in the habit of applying this thought process to other problems as well.
First as usual, let us try to clarify any assumptions:
- Are we talking about any tree or a binary tree. Let us assume for this question that we are talking about a binary tree.
- What is a zig zag tree traversal? Well as the name implies, is a traversal of the tree going zig zag each level, from top to bottom.
- Do we go left-first or right-first? This is actually a great question. A zig zag tree traversal could go both ways, but for simplicity we will assume we want the right zig zag tree traversal.
With these clarification we can visualize a stub tree that would look like this:
This would produce the output: A, B, C, G, F, E, D. Of course this is just a basic binary tree and it’s a good point of start to build our algorithm. There might be multiple edge cases, but let us worry about those later.
To further simplify the question, I decided to first solve the problem of “How to Print an Tree in Level Order Tree Traversal”, meaning we removed the zig zag portion. It would seem somewhat simple to apply the zig zag tree traversal at the end of this.
Now as soon as I read Binary Tree, I immediately thought: Recursion. However, I have done my research about this question and I saw no mention of any recursive solution anywhere, so I decided to take a stab at it on my own.
Level Order Tree Traversal – Recursive Algorithm
- For each level of the tree
- Print nodes in that level
The second step, can be implemented as a recursive function starting from the root and keeping track of your depth. Seems pretty trivial to write out so why don’t we try it out:
Level Order Tree Traversal – Java Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.lang.*; // Level Order Tree Traversal class public class TreeTraversal { public static void printLevelOrder(TreeNode root) { int treeHeight = TreeTraversal.Height(tree); for (int i = 0; i < treeHeight; i++) { TreeTraversal.PrintGivenLevel(tree, i); } } public static int Height(TreeNode root) { if (root == null) { return 0; } return Math.max(Height(root.getLeft())+1, Height(root.getRight())+1); } public static void PrintGivenLevel(TreeNode root, int i) { if (root == null) { return; } if (i == 1) { System.out.println(root.getValue()); } TreeTraversal.PrintGivenLevel(root.getLeft(), i+1); TreeTraversal.PrintGivenLevel(root.getRight(), i+1); } } |
Homework #1: What’s the time and space complexity of the above?
Homework #2: How would you transform the above to print a zig zag tree traversal instead?
As it turns out from the algorithm above which seems unconventional and painfully not performant, using recursion is not really the go-to method for this one. The whole problem lies in the fact that you cannot really solve the main zig zag tree traversals, with sub zig zag tree traversals at child nodes (as is the case for other traversals for example).
So let’s try a different method. We need to go to each level and print out the nodes in one direction or the other. This seems pretty straight forward. The thing that might not be trivial for some is – How do we collect all nodes by level? Well the most clean way is using a BreadthFirstSearch algorithm. So let’s try to first take a stab at printing out a tree level by level first without using recursion. Instead we will just keep track of the depth of each node by putting them all in a Queue one level at a time.
Level Order Tree Traversal – BFS Algorithm
- Starting from the root of the tree:
- Put each node in a queue
- Keep track of the depth for each node
- As you progress keep taking out of the queue, print and put children back in the queue
From this point we just need to invert the way that odd numbered levels are printed.
From a high-level point of view we just need to put odd level nodes in a list and then reverse that list and print it out right when we see an even level. Now for those who are new to this, whenever we need to reverse things, there is a pretty neat data-structure that we can use called Stack. For more info on Stacks and Queues check out nice lecture slide from CMU
Zig Zag Tree Traversal – BFS Algorithm
- Starting from the root of the tree:
- Put each node in a queue
- Keep track of the depth for each node
- As you progress keep taking out of the queue, print and put children back in the queue
Looks like almost all is done. All we have to do is try to put the above into code! So let’s take a stab at it.
Zig Zag Tree Traversal – Java Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.Queue; import java.util.Stack; import java.lang.Math; // Zig Zag Tree Traversal public class TreeTraversal { public static void printZigZagTreeTraversal(TreeNode root) { Queue treeQueue = new Queue<TreeNode>(); Stack reverseStack = new Stack<TreeNode>(); treeQueue.add(root); while (!treeQueue.isEmpty()) { TreeNode node = treeQueue.poll(); if (TreeTraversal.Height(node) % 2 == 0 { TreeTraversal.PrintPopStack(reverseStack); System.out.print("" + node.getValue() + " "); } else { reverseStack.push(node); } treeQueue.add(node.getLeft()); treeQueue.add(node.getRight()); } TreeTraversal.PrintPopStack(reverseStack); } public static int Height(TreeNode root) { if (root == null) { return 0; } return Math.max(Height(root.getLeft())+1, Height(root.getRight())+1); } public static int PrintPopStack(Stack<TreeNode> stack) { while (!stack.empty()) { System.out.print("" + stack.pop().getValue() + " "); } } } |
Homework #3: How does this zig zag tree traversal perform in terms of space and time?
Note that the PrintPopStack method will only print if there is anything in the stack. If we further want to improve the above algorithm, we have to remove the Height lookup. We can do this in two ways:
- Keep track of the height in the tree, so basically in the queue, we would always have a combination of Node-height object/array.
- Get even more tricky and use 2 Stacks. Remember how stacks reverse order. Well if we use them twice, they will reverse order twice, meaning the order will be maintained. Now you will only need a flag to tell you if to use the second stack (meaning order normal), or not (meaning order reversed)
Homework #4: Can you implement both of these on your spare time?
So to wrap up, hope you enjoyed this type of step by step detailed guide going from basic recursion to how to write full code for a zig zag tree traversal question. Next time, rather than memorizing solutions, you can just try to simplify and divide the questions into sub-problems and find a solution one step at a time.
Hope you guys enjoyed it! And I’ll see you guys next time ;D.
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017