Traverse a binary tree in level order is intuitive. We can initialize a queue and add elements. Every cycle you need to print out the nodes in the queue, and add their children to queue, until queue is empty.
However, since the recursive solution for pre-order, in-order, and post-order traverse is quite easy, I wonder if level traverse is also simple. I think about it and finally had a solution. Though it’s simple, it’s different from the traverse mentioned above.
|
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 |
public class LevelTraverse { public static class TreeNode{ public TreeNode left; public TreeNode right; public int data; public TreeNode(int data){ this.left = null; this.right = null; this.data = data; } } public static void recursiveTraverse(TreeNode root, int level){ if(root==null) return; if(level==1){ System.out.println(root.data); return; } recursiveTraverse(root.left,level-1); recursiveTraverse(root.right,level-1); } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.right = new TreeNode(4); root.right = new TreeNode(3); root.right.left = new TreeNode(5); root.right.right = new TreeNode(6); int height = 3; for(int i=1;i<=height;i++){ recursiveTraverse(root,i); } } } |
In this code I test a simple tree. To use the function, you need to know the height of the tree. It’s very easy to know using recursion.
In the for cycle, we print out data of nodes of each level. The recursive function is simple. It outputs data only when level=1. Otherwise it will try to output its next level.