Implement InOrderWalk algorithm JAVA Your function must take

Implement InOrderWalk algorithm (JAVA). Your function must take an ArrayList as input and produce another ArrayList as output where the elements are arranged according to the in-order. Included all classes (Node, tree, etc.) Test InOrderWalk method in main method. Figure 1: A binary tree. root: 100 root.left = 50; root.right = 200 root.left(50).left = 40; root.left(50).right = 200 root.left(50).left(40).left = 30; root.left(50).left(40).right = 60 The binary tree from above will be represented as: {{100}, {50, 200}, {40, 200, null, null}, {30, 60, null, null, null, null, null, null}} Please, read input from the text file input.txt. For the example above, the contents of the file should look like: 100 50,200 40,200,null,null 30,60,null,null,null,null,null,null Output the nodes in-order to the standard output (screen). So, your function should look something like: void InOrderWalk(ArrayList

Solution

// method to perform the inorder walk
   void InOrderWalk(ArrayList<ArrayList<Integer» bst,TreeNode tr_rt)
   {
        // code to create stack
        Stack<TreeNode> stack = new Stack<TreeNode>();      
        TreeNode tr_node = tr_rt;
       // code to perform inorder walk
        while (!stack.isEmpty() || tr_node != null)
       {
            if (tr_node != null)
           {
                stack.push(tr_node);
                tr_node = tr_node.left;
            }
           else
           {
                tr_node = stack.pop();
                bst.add(tr_node.val);
                tr_node = tr_node.right;
            }
        }
        System.out.println(Arrays.toString(result));
   }