Friday, November 2, 2012

Binary Tree: level order linked list


Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).

Approach:
We can do breadth first traversal of the tree keeping track of the levels, and create a linkedlist of all the nodes at any particular level

Input/Output:
iterative inorder:
3 7 9 15 17 21 25
printing level order:
15
7 21
3 9 17 25

Printing linked list at each level:
Level: 0
15
Level: 1
7 21
Level: 2
3 9 17 25

No comments:

Post a Comment