Level Order Traversal of a Binary Tree in JavaThe breadth first traversal of a binary tree is also known as the level order traversal of a binary tree in Java. For the following binary tree: The level order traversal is: 18 20 30 60 34 45 65 12 50 98 82 31 59 71 41 Using RecursionOne can do the level order traversal of a binary tree using recursion. In the recursive approach, we have to take care of the left and right subtrees. The pseudocode shows the same in more detail. Pseudo Code of the recursive approachImplementationLet's implement the level order traversal of the binary tree using the pseudocode defined above. FileName: BTreeLevelOrder.java Output: Level order traversal of binary tree is 18 20 30 60 34 45 65 12 50 98 82 31 59 71 41 Time Complexity: The time complexity of the program is O(n^2) in the worst case, where n is the total number of nodes of a binary tree. Note that the worst scenario occurs when the tree is skewed. Space Complexity: The space complexity of the program is O(n) in the worst case, where n is the total number of nodes of a binary tree. Note that the worst scenario occurs when the tree is skewed. For a skewed tree, the displayCurrentLevel() method uses the O(n) space for the call stack. In our case, the tree is balanced; therefore, the space used is O(log(n)), which is the height of a balanced tree. Using QueueOne can also accomplish the level order traversal of a binary tree using a queue. Using queue, first, we put all of the children of a node in a queue. The left child is put first in the queue, followed by the right child. As a queue works on the FIFO (First In First Out) principle, the left child comes out first, then the right child, and thus, the level ordered traversal of the tree is achieved. For better understanding, let's observe the pseudocode then its implementation. Pseudo Code for traversal using queueImplementationLet's implement the level order traversal of the binary tree using the pseudocode defined above. FileName: BTreeLevelOrder1.java Output: Level order traversal of binary tree is: 18 20 30 60 34 45 65 12 50 98 82 31 59 71 41 Time Complexity: The time complexity of the program is O(n), where n is the total number of nodes of a binary tree. Space Complexity: The space complexity of the program is also O(n), where n is the total number of nodes of a binary tree. Comparison of Both the ApproachesBy comparing the time and space complexities of both the approaches, we find the using queue; we achieve the result much quicker. Also, the time complexity, as well as the space complexity of the queue program, is not dependent on the arrangement of nodes. It means, even if the tree is skewed, the time and space complexity of the program does not change, and such thing is not possible with the recursive approach. In the recursive approach, it matters a lot on the arrangement of nodes of the tree.
Next TopicBully algorithm in Java
