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 :
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.
Thanks for pointing it out. Just corrected it.
Thanks for reading.
:)
Post a Comment