java program – Level Order Tree Traversal

Level order traversal of a tree is breadth first traversal for the tree.

Level order traversal of the above tree is 1 2 3 4 5

METHOD 1 (Use function to print a given level)

Algorithm:
There are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.

/*Function to print level order traversal of tree*/
printLevelorder(tree)
for d = 1 to height(tree)
   printGivenLevel(tree, d);

/*Function to print all nodes at a given level*/
printGivenLevel(tree, level)
if tree is NULL then return;
if level is 1, then
    print(tree->data);
else if level greater than 1, then
    printGivenLevel(tree->left, level-1);
    printGivenLevel(tree->right, level-1);

[ad type=”banner”] [pastacode lang=”java” manual=”%2F%2F%20Recursive%20Java%20program%20for%20level%20order%20traversal%20of%20Binary%20Tree%0A%20%0A%2F*%20Class%20containing%20left%20and%20right%20child%20of%20current%20%0A%20%20%20node%20and%20key%20value*%2F%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20left%2C%20right%3B%0A%20%20%20%20public%20Node(int%20item)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20item%3B%0A%20%20%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Aclass%20BinaryTree%0A%7B%0A%20%20%20%20%2F%2F%20Root%20of%20the%20Binary%20Tree%0A%20%20%20%20Node%20root%3B%0A%20%0A%20%20%20%20public%20BinaryTree()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20root%20%3D%20null%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20function%20to%20print%20level%20order%20traversal%20of%20tree*%2F%0A%20%20%20%20void%20printLevelOrder()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20h%20%3D%20height(root)%3B%0A%20%20%20%20%20%20%20%20int%20i%3B%0A%20%20%20%20%20%20%20%20for%20(i%3D1%3B%20i%3C%3Dh%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20printGivenLevel(root%2C%20i)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Compute%20the%20%22height%22%20of%20a%20tree%20–%20the%20number%20of%0A%20%20%20%20nodes%20along%20the%20longest%20path%20from%20the%20root%20node%0A%20%20%20%20down%20to%20the%20farthest%20leaf%20node.*%2F%0A%20%20%20%20int%20height(Node%20root)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20compute%20%20height%20of%20each%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20lheight%20%3D%20height(root.left)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20rheight%20%3D%20height(root.right)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20use%20the%20larger%20one%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(lheight%20%3E%20rheight)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return(lheight%2B1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20return(rheight%2B1)%3B%20%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Print%20nodes%20at%20the%20given%20level%20*%2F%0A%20%20%20%20void%20printGivenLevel%20(Node%20root%20%2Cint%20level)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20if%20(level%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(root.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20else%20if%20(level%20%3E%201)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20printGivenLevel(root.left%2C%20level-1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20printGivenLevel(root.right%2C%20level-1)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20BinaryTree%20tree%20%3D%20new%20BinaryTree()%3B%0A%20%20%20%20%20%20%20tree.root%3D%20new%20Node(1)%3B%0A%20%20%20%20%20%20%20tree.root.left%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20tree.root.right%3D%20new%20Node(3)%3B%0A%20%20%20%20%20%20%20tree.root.left.left%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20tree.root.left.right%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20System.out.println(%22Level%20order%20traversal%20of%20binary%20tree%20is%20%22)%3B%0A%20%20%20%20%20%20%20tree.printLevelOrder()%3B%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/]