public class New { static Node e; public static class Node { private int data; private Node left, right; public Node( int d ) {data=d;} public Node( Node l, Node r ) {data=-1; left=l; right=r;} public boolean isSingleNode() {return left==null && right==null;} private void leftRotate() { // A(BC) => (AB)C (basic associativity law) left = new Node( left, right.left ); right = right.right; e.println(); // print the whole expression } // rewrites `this' tree to the `standard' tree which evaluates from left to right public void LeftToRight() { if (isSingleNode()) {} else if (right.isSingleNode()) {left.LeftToRight();} else {leftRotate(); LeftToRight();} } // codes for printing a binary tree is adapted from // // http://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram // // credits go to Vasya Novikov and Todd Davies // private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) { if(right!=null) right.toString(new StringBuilder().append(prefix).append(isTail ? "? " : " "), false, sb); sb.append(prefix).append(isTail ? "??? " : "??? ").append(data==-1?"?":data).append(" "); if(left !=null) left.toString(new StringBuilder().append(prefix).append(isTail ? " " : "? "), true, sb); return sb; } public void println() { System.out.println(this.toString(new StringBuilder(), true, new StringBuilder()).toString()); } } public static void main (String[] args) { // r3t4 = ( 3 4 ) Node r3t4 = new Node( new Node(3) , new Node(4) ); // r2t4 = ( 2 ( 3 4 )) Node r2t4 = new Node( new Node(2) , r3t4 ); // r8t9 = ( 8 9 ) Node r8t9 = new Node( new Node(8) , new Node(9) ); // r7t9 = ( 7 ( 8 9 )) Node r7t9 = new Node( new Node(7) , r8t9 ); // r7t10 = (( 7 ( 8 9 )) 10) Node r7t10 = new Node( r7t9, new Node(10) ); // r6t10 = ( 6 (( 7 ( 8 9 )) 10)) Node r6t10 = new Node( new Node(6), r7t10); // r6t11 = (( 6 (( 7 ( 8 9 )) 10)) 11) Node r6t11 = new Node( r6t10, new Node(11) ); // r5t11 = ( 5 (( 6 (( 7 ( 8 9 )) 10)) 11)) Node r5t11 = new Node( new Node(5), r6t11 ); // r5t12 = (( 5 (( 6 (( 7 ( 8 9 )) 10)) 11)) 12) Node r5t12 = new Node( r5t11, new Node(12) ); // r2t12 = (( 2 ( 3 4 ))(( 5 (( 6 (( 7 ( 8 9 )) 10)) 11)) 12)) Node r2t12 = new Node( r2t4, r5t12 ); // r2t13 = ((( 2 ( 3 4 ))(( 5 (( 6 (( 7 ( 8 9 )) 10)) 11)) 12)) 13) Node r2t13 = new Node( r2t12, new Node(13) ); // r1t13 = ( 1 ((( 2 ( 3 4 ))(( 5 (( 6 (( 7 ( 8 9 )) 10)) 11)) 12)) 13)) Node r1t13 = new Node( new Node(1), r2t13 ); e = r1t13; // e is a global static variable e.println(); e.LeftToRight(); } } 

Q. : Argue in plain English that when LeftToRight halts, the tree returned is the standard left-to-right evaluation tree. (That is, in your arguments, you can assume without proof that the program must halt.)