package
com.kartik.org; public class
BinaryTreeLevelOrder { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data=data; } } // prints in level order left to right public static boolean
levelOrderTraversalLeftToRight(TreeNode startNode,int level) { if(null == startNode){ return false; } if(level == 1){ System.out.println(startNode.data+"
"); return true; } boolean left
=levelOrderTraversalLeftToRight(startNode.left, level-1); boolean right
=levelOrderTraversalLeftToRight(startNode.right, level-1); return left || right; } public static void
levelOrderTraversalLeftToRight(TreeNode startNode) { if(null == startNode){ return; } int level=1;
while(levelOrderTraversalLeftToRight(startNode, level++)){ } } //print right to left public static boolean
levelOrderTraversalRightToLeft(TreeNode startNode,int level) { if(null == startNode){ return false; } if(level == 1){ System.out.println(startNode.data+"
"); return true; } boolean right
=levelOrderTraversalRightToLeft(startNode.right, level-1); boolean left
=levelOrderTraversalRightToLeft(startNode.left, level-1); return right || left; } public static void
levelOrderTraversalRightToLeft(TreeNode startNode) { if(null == startNode){ return; } int level=1;
while(levelOrderTraversalRightToLeft(startNode, level++)){ System.out.println("---"); } } public static void main(String[] args) { // Creating a binary tree TreeNode rootNode=createBinaryTree(); System.out.println("Level Order
traversal of binary tree will be left to Right -->:"); levelOrderTraversalLeftToRight(rootNode); System.out.println("Level Order
traversal of binary tree will be Right to Left -->:"); levelOrderTraversalRightToLeft(rootNode); } public static TreeNode createBinaryTree() { TreeNode rootNode =new TreeNode(40); TreeNode node20=new TreeNode(20); TreeNode node10=new TreeNode(10); TreeNode node30=new TreeNode(30); TreeNode node60=new TreeNode(60); TreeNode node50=new TreeNode(50); TreeNode node70=new TreeNode(70); rootNode.left=node20; rootNode.right=node60; node20.left=node10; node20.right=node30; node60.left=node50; node60.right=node70; return rootNode; } } |
The provided Java code demonstrates a binary tree structure
and implements two traversal methods: level-order traversal from left to right
and level-order traversal from right to left. Below is an explanation of the
code.
Explanation:
- TreeNode
Class:
- A
static inner class TreeNode represents a node in the binary tree. It has
three fields:
- int
data: Stores the value of the node.
- TreeNode
left: Reference to the left child node.
- TreeNode
right: Reference to the right child node.
- The
constructor TreeNode(int data) initializes the node with the provided
value.
- Level
Order Traversal from Left to Right:
- levelOrderTraversalLeftToRight(TreeNode
startNode, int level):
- This
method recursively traverses the tree level by level, starting from the
given startNode.
- If
the level is 1, it prints the node's data.
- It
recursively calls itself for the left and right subtrees, reducing the
level by 1 in each recursive call.
- It
returns true if the traversal is successful, or false if the startNode
is null.
- levelOrderTraversalLeftToRight(TreeNode
startNode):
- This
method initiates the level-order traversal by calling the previous
method with increasing levels until no nodes are left to traverse.
- Level
Order Traversal from Right to Left:
- levelOrderTraversalRightToLeft(TreeNode
startNode, int level):
- Similar
to the left-to-right traversal method, but the order of traversal is
reversed.
- It
starts with the right subtree first, followed by the left subtree.
- levelOrderTraversalRightToLeft(TreeNode
startNode):
- This
method initiates the right-to-left traversal by calling the previous
method with increasing levels until no nodes are left to traverse.
- Main
Method:
- The main
method creates a binary tree using the createBinaryTree() method.
- It
then prints the tree in level order from left to right and right to left
using the corresponding traversal methods.
- Binary
Tree Structure:
- The createBinaryTree()
method builds a binary tree with the following structure:
markdown
40 /
\ 20
60 /
\ / \ 10
30 50 70 |
- This
tree is used as the input for the traversal methods.
Output:
When you run the code, the output will be:
text
Level Order
traversal of binary tree will be left to Right -->: 40 20 60 10 30 50 70 Level Order
traversal of binary tree will be Right to Left -->: 40 60 20 70 50 30 10 |
Summary:
- Left-to-right
traversal prints nodes level by level starting from the leftmost node
on each level.
- Right-to-left
traversal prints nodes level by level starting from the rightmost node
on each level.
0 Comments