Tuesday, August 13, 2013

Binary Tree Level-Order Traversal

Problem:

Yesterday(8/12/2013), I was asked to implement this problem Binary Tree Level-Order Traversal in a short time. For the first thought, it looks like an easy BFS problem, but quickly I realize a problem how can I track the level of the tree? Haha...

At the end, I gave my solution, but the interviewee said my solution is most weird one he has ever seen. LOL... I don't know what will be coming for me, but it's a great experience, and we'll see.

The following are my solutions for this problem with different strategy. Have Fun.

PS: every solution I provided uses Linear time and space. Approvement might be attached.

Source Code:


  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
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
/**
 * This is a demo class in java <br />
 * Implementing Binary Tree Traverse Level By Level with BFS and DFS. <br /> 
 * All of the algorithm I implemented use O(N) time, N here represents the number of nodes in the tree.
 * 
 */
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Antonio081014
 * @since Aug 13, 2013, 9:22:40 AM
 */
public class Solution {

 public static void main(String[] args) {
  Solution main = new Solution();
  Node root = main.new Node("3");
  root.left = main.new Node("9");
  root.right = main.new Node("20");
  root.right.left = main.new Node("15");
  root.right.right = main.new Node("7");
  main.printLevelOrder_Option4(root);
  System.exit(0);
 }

 /**
  * Tree node structure;
  * */
 class Node {
  String value;
  Node left;
  Node right;

  public Node(String v) {
   value = v;
   left = null;
   right = null;
  }
 }

 /**
  * This is the answer I gave when I was in the interview.<br />
  * Basically, track the number of children we counted, if all the children
  * in that level is counted, then we print a newline and increase the tree
  * level; The flaw of this algorithm is it can not take too many levels,
  * since integer in java can't exceed 2^32; which means we maximumly will
  * have 32 levels, even if we use long instead of int, this one is still not
  * a good choice.
  * */
 private void printLevelOrder_Option0(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  int level = 1;
  int count = 0;
  queue.add(root);
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   if (count == 0)
    System.out.print(node.value);
   else
    System.out.print(" " + node.value);

   if (node.left != null)
    queue.add(node.left);
   if (node.right != null)
    queue.add(node.right);
   count += 2;

   if (count == (int) Math.pow(2, level)) {
    System.out.println();
    level++;
    count = 0;
   }
  }
 }

 /**
  * Generally, this algorithm uses BFS, which involves two queues keep tracks
  * of node in current level and nodes in next leve;<br />
  * Basically,<br />
  * 1, When a node is extracted, we print it, while adding its children to
  * the next level if they are not null;<br />
  * 2, When current level queue is empty, which means all of the current
  * nodes are extracted and printed, also all the children of current level
  * nodes are added to the next level queue. So we could just copy every
  * single node in next level queue and add it to the current queue, and
  * print the newline.
  * */
 private void printLevelOrder_Option1(Node root) {
  if (root == null)
   return;
  Queue<Solution.Node> currentLevel = new LinkedList<Solution.Node>();
  Queue<Solution.Node> nextLevel = new LinkedList<Solution.Node>();
  currentLevel.add(root);
  while (!currentLevel.isEmpty()) {
   Solution.Node node = currentLevel.poll();
   System.out.print(node.value + " ");
   if (node.left != null)
    nextLevel.add(node.left);
   if (node.right != null)
    nextLevel.add(node.right);
   if (currentLevel.size() == 0) {
    System.out.println();
    while (!nextLevel.isEmpty()) {
     currentLevel.add(nextLevel.poll());
    }
   }
  }
 }

 /**
  * For this algorithm, we use two counters to keep track of number of nodes
  * in current level, and the number of nodes in next level; <br />
  * This idea is very similar with printLevelOrder_Option1(Node root),
  * however, it uses less memory and doesn't need to copy each node from one
  * queue to another.
  * */
 private void printLevelOrder_Option2(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  int nodesInCurrentLevel = 0;
  int nodesInNextLevel = 0;
  queue.add(root);
  nodesInCurrentLevel++;
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   System.out.print(" " + node.value);
   nodesInCurrentLevel--;
   if (node.left != null) {
    queue.add(node.left);
    nodesInNextLevel++;
   }
   if (node.right != null) {
    queue.add(node.right);
    nodesInNextLevel++;
   }
   if (nodesInCurrentLevel == 0) {
    System.out.println();
    nodesInCurrentLevel = nodesInNextLevel;
    nodesInNextLevel = 0;
   }
  }
 }

 /**
  * This algorithm uses a trick of BFS.<br />
  * Since we are using BFS to traverse this binary tree level by level in a
  * very nature way. We just add a newline node at the very beginning, then
  * if this newline node is reached, that means all of nodes of current nodes
  * has been visited, so we are going to move to the next level, then print
  * the newline here.
  * 
  * This trick uses the nature of BFS in binary, very smart. I think the
  * interviewee was trying to ignite me to this solution. Somehow, I didn't
  * get it. For this algorithm, user could replace this newline node with
  * other flag node for other purposes.
  * */
 private void printLevelOrder_Option3(Node root) {
  if (root == null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  queue.add(new Node("\n"));
queue.add(new Node("\n"));
  while (queue.size() > 1) {
   Node node = queue.poll();
   System.out.print(node.value + " ");
   if (node.value.compareTo("\n") == 0) {
    queue.add(node);
    continue;
   }
   if (node.left != null)
    queue.add(node.left);
   if (node.right != null)
    queue.add(node.right);
  }
 }

 /**
  * This algorithm uses DFS;<br />
  * 1, Get the height from root tree node.<br />
  * 2, For each level, print the nodes on that level with a newline.
  * 
  * Although the DFS solution traverse the same node multiple times, it is
  * not another order slower than the BFS solution. Here is the proof that
  * the DFS solution above runs in O(N) time, where N is the number of nodes
  * in the binary tree and we assume that the binary tree is balanced.
  * 
  * We first compute the complexity of printLevel for the kth level:
  * 
  * T(k) <br />
  * = 2T(k-1) + c <br />
  * = 2k-1 T(1) + c <br />
  * = 2k-1 + c
  * 
  * Assuming it’s a balanced binary tree, then it would have a total of lg N
  * levels. Therefore, the complexity of printing all levels is:
  * 
  * T(1) + T(2) + ... + T(lg N) = 1 + 2 + 22 + ... + 2lg N-1 + c = O(N)
  * Finding the maximum height of the tree also takes O(N) time, therefore
  * the overall complexity is still O(N).
  * */
 private void printLevelOrder_Option4(Node root) {
  int height = treeLevel(root);
  for (int i = 1; i <= height; i++) {
   printLevel(root, i);
   System.out.println();
  }
 }

 /**
  * Print the nodes on Level: level.
  * */
 private void printLevel(Node root, int level) {
  if (root == null)
   return;
  if (level == 1) {
   System.out.print(root.value + " ");
  } else {
   printLevel(root.left, level - 1);
   printLevel(root.right, level - 1);
  }
 }

 private int treeLevel(Node root) {
  if (root == null)
   return 0;
  return 1 + Math.max(treeLevel(root.left), treeLevel(root.right));
 }
}

2 comments :

Yi Ding said...

Thanks for posting different solution.In your option 3 printLevelOrder_Option3 the queue.add(new Node("\n")) should be after adding the root else it will go in infinite loop.

Yi Ding said...

Thanks for pointing it out. Just corrected it.
Thanks for reading.
:)