Tree-Traverse-Order-Level-Frame

import java.util.*;

// structure of the node of the binary tree
class Node{
    int data;
    Node left;
    Node right;
    public Node(int data)
    {
        this.data=data;
    }
}
public class TraversTreeAndFrame {

    static ArrayList<Object[]> traversal;

    // function to traverse the binary
    // tree in the level order fashion
    public static void levelOrderTraversal(Node root)
    {
        // current node is marked as the root node
        Node curr=root;
        int level=0;
        // loop to traverse the binary tree until the current node
        // is not null
        while(curr!=null)
        {
            // if left child is null, print the
            // current node data and update the
            // current pointer to right child.
            if(curr.left==null)
            {
                // return the current node with
                // its level
                traversal.add(new Object[]{curr,new Integer(level)});
                curr=curr.right;
                if(curr!=null)
                {
                    level++;
                }else
                    level--;
            }
            else{
                // find the inorder predecessor
                Node prev=curr.left;
                int toUp=0;

                // loop to find the right most
                // node of the left child of the current node
                while(prev.right!=null && prev.right!=curr)
                {
                    prev=prev.right;
                    toUp++;
                }
                // If the right child of inorder
                // predecessor already points to
                // the current node, update the
                // current with it's right child
                if(prev.right==curr)
                {
                    prev.right=null;
                    curr=curr.right;
                    level-=toUp+1;
                }
                // else If right child doesn't
                // point to the current node,
                // then print this node's data
                // and update the right child
                // pointer with the current node
                // and update the current with
                // it's left child
                else{
                    traversal.add(new Object[]{curr,new Integer(level)});
                    prev.right=curr;
                    curr=curr.left;
                    level++;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        // create a binary tree
        Node root=new Node(5);
        root.left=new Node(2);
        root.right=new Node(3);
        root.left.right=new Node(6);
        root.right.left=new Node(7);
        root.right.right=new Node(8);
        traversal=new ArrayList<>();

        // traverse the tree in level order traversal
        levelOrderTraversal(root);

        // find the height of the tree
        int h=0;
        for(Object[] i:traversal)
        {
            h=Math.max(h,(int)i[1]+1);
        }

        // print the date of nodes at each level
        for(int i = 0; i<h; i++){
            for(Object[] j : traversal){
                if((int)j[1] == i){

                    System.out.print(((Node)j[0]).data+" ");
                }
            }
            System.out.println();
        }
    }
  //Time Complexity: As in the above approach, every node is
    // touched at max twice due to which the time complexity is O(N),
    // where N is the number of nodes.
    //Auxiliary Space: As in the above approach,
    // there is no extra space used due to which auxiliary space used will be O(1) 
  
    
}