Tree : Level-Order-Traversal or Breath-First-Search

In this post, I will summarize a Binary’s Search Trees (BST)s, level order traversal. I picked this problem from HackerRank Site and feel like, its been touch based so much every where it needs a place where the problem and solution can be easily searched and read. So here we go…

Problem

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function and print the values in a single line separated by a space.

For example:

1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

For the above tree, the level order traversal is 1 2 5 3 6 4 .

Input Format

You are given a function,

void levelOrder(Node * root) {}

Constraints

1≤Nodes in the tree ≤ 500

Output Format

Print the values in a single line separated by a space.

Sample Input

1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

Sample Output

1 2 5 3 6 4

Explanation

We need to print the nodes level by level. We process each level from left to right.

Solution

from collections import deque
# Declare a queue to maintain order.
queue = deque()
def levelOrder(root):
    queue.append(root) 
   
    while(len(queue) > 0):
        node = queue.popleft()
# process the node of the leftmost node in the queue.
        print(node.info, end=" ")
        
        # append the left child followed 
        # by the right child in the queue for processing.           
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
# HELPER CLASSES AND FUNCTIONS
"""
Node is defined as
self.left (the left child of the node)
self.right (the right child of the node)
self.info (the value of the node)
"""
class Node:
    def __init__(self, info): 
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None  
    # Just for fun, override the __str__ so that a print on node gives its info.   
    def __str__(self):
        return str(self.info)
### A BST only has a one instance variable. A root 
### which is the pointer to the root node of BST.
### We create the BST node-by-node in create function.
class BinarySearchTree:
    def __init__(self): 
        self.root = None  
      
    def create(self, val):  
        if self.root == None:
            self.root = Node(val)
        else:
            current = self.root            
            while True:
                if val < current.info:
                    if current.left:
                        current = current.left
                    else:
                        current.left = Node(val)
                        break
                elif val > current.info:
                    if current.right:
                        current = current.right
                    else:
                        current.right = Node(val)
                        break
                else:
                    break
tree = BinarySearchTree()
# Input size of the BST tree in first line.
t = int(input())
## In the second line, Supply all BST values in space separated line.
arr = list(map(int, input().split()))
## Create the BST from one input at a time.
for i in range(t):
    tree.create(arr[i])
# Print the Breath first search of the Tree.
levelOrder(tree.root)

Input

116
37 23 108 59 86 64 94 14 105 17 111 65 55 31 79 97 78 25 50 22 66 46 104 98 81 90 68 40 103 77 74 18 69 82 41 4 48 83 67 6 2 95 54 100 99 84 34 88 27 72 32 62 9 56 109 115 33 15 91 29 85 114 112 20 26 30 93 96 87 42 38 60 7 73 35 12 10 57 80 13 52 44 16 70 8 39 107 106 63 24 92 45 75 116 5 61 49 101 71 11 53 43 102 110 1 58 36 28 76 47 113 21 89 51 19 3

Output

37 23 108 14 31 59 111 4 17 25 34 55 86 109 115 2 6 15 22 24 27 32 35 50 56 64 94 110 114 116 1 3 5 9 16 18 26 29 33 36 46 54 57 62 65 90 105 112 7 12 20 28 30 40 48 52 58 60 63 79 88 91 97 107 113 8 10 13 19 21 38 41 47 49 51 53 61 78 81 87 89 93 95 104 106 11 39 42 66 80 82 92 96 98 44 68 83 103 43 45 67 77 84 100 74 85 99 101 69 75 102 72 76 70 73 71

Another Input

418
13 105 278 16 60 135 47 129 234 372 271 179 189 103 302 71 377 4 112 195 360 151 348 125 393 351 236 409 68 371 210 149 255 37 24 259 243 10 91 98 126 160 308 229 297 107 95 353 175 172 191 163 379 137 386 49 67 405 257 110 199 15 327 416 184 22 38 148 383 374 200 138 263 158 339 19 132 50 79 370 401 230 34 190 48 176 41 162 346 28 64 202 414 222 161 334 76 127 244 306 96 399 177 88 239 33 73 356 344 3 45 58 219 311 332 231 156 284 204 106 178 59 44 194 237 226 354 247 99 335 304 186 410 266 114 185 81 341 92 113 375 368 55 256 396 78 218 281 197 7 72 143 395 277 46 358 282 382 142 187 251 310 290 285 57 328 292 352 317 180 82 323 364 89 260 128 119 217 100 153 397 388 164 173 345 8 43 343 196 155 307 331 117 144 301 26 272 340 324 134 240 120 337 77 391 407 201 168 250 312 17 289 53 35 5 303 14 270 192 108 208 369 390 253 147 299 305 213 400 363 373 181 295 261 309 145 298 205 408 349 29 269 152 367 413 279 238 62 102 116 392 40 51 254 140 74 227 165 330 27 63 315 54 258 85 12 104 357 118 241 31 193 198 122 130 183 361 274 291 25 146 121 321 268 273 36 316 216 70 171 75 380 296 66 264 398 359 87 338 355 220 288 225 21 94 157 207 86 97 235 83 381 221 61 42 111 150 320 188 123 300 215 329 267 170 18 167 224 265 293 23 124 212 39 376 326 378 169 415 65 365 394 245 182 211 242 350 336 385 342 233 84 283 228 154 166 418 206 389 214 133 347 232 275 52 402 287 2 318 93 280 248 313 1 131 209 412 406 249 325 276 6 286 9 333 403 314 262 387 30 56 362 141 11 109 417 136 139 322 223 246 101 80 294 404 319 32 69 20 115 174 366 252 90 384 159 411 203

Expected output

13 4 105 3 10 16 278 2 7 12 15 60 135 372 1 5 8 11 14 47 103 129 234 302 377 6 9 37 49 71 104 112 132 179 271 297 360 374 393 24 38 48 50 68 91 107 125 130 134 151 189 236 277 284 301 348 371 373 375 379 409 22 34 41 58 67 70 79 98 106 110 114 126 131 133 149 160 184 195 235 255 272 281 290 299 308 351 370 376 378 386 405 416 19 23 28 35 40 45 55 59 64 69 76 88 95 99 108 111 113 119 127 137 150 158 175 180 186 191 210 243 259 274 279 282 285 292 298 300 306 327 349 353 368 383 388 401 407 414 418 17 21 26 33 36 39 44 46 53 57 62 66 73 78 81 89 92 96 100 109 117 120 128 136 148 156 159 172 176 181 185 187 190 194 199 229 239 244 257 263 273 275 280 283 289 291 295 304 307 311 339 350 352 356 364 369 382 385 387 391 399 402 406 408 410 415 417 18 20 25 27 29 43 51 54 56 61 63 65 72 74 77 80 82 90 94 97 102 116 118 122 138 153 157 163 173 177 183 188 192 197 200 222 230 237 240 247 256 258 260 266 276 288 293 296 303 305 310 317 334 346 354 358 363 367 380 384 390 392 396 400 403 413 31 42 52 75 85 93 101 115 121 123 143 152 155 162 164 174 178 182 193 196 198 202 219 226 231 238 241 245 251 261 264 270 287 294 309 312 323 332 335 344 347 355 357 359 361 365 381 389 395 397 404 412 30 32 83 87 124 142 144 154 161 168 201 204 218 220 225 227 233 242 246 250 253 262 265 269 286 315 321 324 328 333 337 341 345 362 366 394 398 411 84 86 140 147 165 171 203 208 217 221 224 228 232 248 252 254 268 313 316 320 322 326 331 336 338 340 343 139 141 145 167 170 205 209 213 223 249 267 314 318 325 330 342 146 166 169 207 212 216 319 329 206 211 215 214