{"id":27144,"date":"2018-01-03T21:50:24","date_gmt":"2018-01-03T16:20:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27144"},"modified":"2018-01-03T21:50:24","modified_gmt":"2018-01-03T16:20:24","slug":"java-program-level-order-tree-traversal","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-level-order-tree-traversal\/","title":{"rendered":"java program – Level Order Tree Traversal"},"content":{"rendered":"

Level order traversal of a tree is breadth first traversal for the tree.<\/p>\n

Level order traversal of the above tree is 1 2 3 4 5<\/p>\n

\n

Recommended: Please solve it on “PRACTICE<\/u><\/i><\/b>” first,<\/h2>\n

before moving on to the solution.<\/h2>\n<\/div>\n

METHOD 1 (Use function to print a given level)<\/strong><\/p>\n

Algorithm:<\/strong>
\nThere 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.<\/p>\n

\/*Function to print level order traversal of tree*\/\r\nprintLevelorder(tree)<\/strong>\r\nfor d = 1 to height(tree)\r\n   printGivenLevel(tree, d);\r\n\r\n\/*Function to print all nodes at a given level*\/\r\nprintGivenLevel(tree, level)<\/strong>\r\nif tree is NULL then return;\r\nif level is 1, then\r\n    print(tree->data);\r\nelse if level greater than 1, then\r\n    printGivenLevel(tree->left, level-1);\r\n    printGivenLevel(tree->right, level-1);<\/pre>\n[ad type=”banner”]\n
 
 <\/div> 
\/\/ Recursive Java program for level order traversal of Binary Tree \/* Class containing left and right child of current    node and key value*\/class Node{    int data;    Node left, right;    public Node(int item)    {        data = item;        left = right = null;    }} class BinaryTree{    \/\/ Root of the Binary Tree    Node root;     public BinaryTree()    {        root = null;    }     \/* function to print level order traversal of tree*\/    void printLevelOrder()    {        int h = height(root);        int i;        for (i=1; i<=h; i++)            printGivenLevel(root, i);    }     \/* Compute the "height" of a tree -- the number of    nodes along the longest path from the root node    down to the farthest leaf node.*\/    int height(Node root)    {        if (root == null)           return 0;        else        {            \/* compute  height of each subtree *\/            int lheight = height(root.left);            int rheight = height(root.right);                         \/* use the larger one *\/            if (lheight > rheight)                return(lheight+1);            else return(rheight+1);         }    }     \/* Print nodes at the given level *\/    void printGivenLevel (Node root ,int level)    {        if (root == null)            return;        if (level == 1)            System.out.print(root.data + " ");        else if (level > 1)        {            printGivenLevel(root.left, level-1);            printGivenLevel(root.right, level-1);        }    }         \/* Driver program to test above functions *\/    public static void main(String args[])    {       BinaryTree tree = new BinaryTree();       tree.root= new Node(1);       tree.root.left= new Node(2);       tree.root.right= new Node(3);       tree.root.left.left= new Node(4);       tree.root.left.right= new Node(5);               System.out.println("Level order traversal of binary tree is ");       tree.printLevelOrder();    }}<\/code><\/pre> <\/div>\n","protected":false},"excerpt":{"rendered":"
java program – Level Order Tree Traversal – Level order traversal of tree is breadth first traversal for the tree. There are basically two functions <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80140,1,2139],"tags":[80965,80963,80964,80908,80903,80906,80962,80966],"class_list":["post-27144","post","type-post","status-publish","format-standard","hentry","category-binay-tree","category-coding","category-java","tag-binary-tree-level-order-traversal-ii","tag-binary-tree-level-order-traversal-java","tag-binary-tree-level-order-traversal-leetcode","tag-level-order-traversal-example","tag-level-order-traversal-of-a-binary-tree-in-c-code","tag-level-order-traversal-of-binary-tree-using-queue-in-c","tag-level-order-traversal-using-queue","tag-zigzag-level-order-traversal"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27144","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27144"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27144\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27144"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27144"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27144"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}