Node pre;
    if(root == null)
        return;
    Node curr = root;
    while(curr != null){
        if(curr.left == null){
            System.out.print(curr.data+" ");
            curr = curr.right;
        }else{
             pre = curr.left;
             while(pre.right !=null && pre.right != curr)
                 pre = pre.right;
             if(pre.right == null){
                 pre.right = curr;
                 System.out.print(curr.data+" ");
                 curr = curr.left;
             }else{
                 pre.right=null;
                 curr=curr.right;
             }
        }
    }

void preOrder(Node root) {
    if(root==null){
        return ;
    }
    System.out.print(root.data+" ");
    preOrder(root.left);
    preOrder(root.right);
}

public static void preOrder(Node root) {
    if (root == null) return;
    System.out.print(root.data + " ");
    preOrder(root.left);
    preOrder(root.right);
}

public static void preOrder(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node node = stack.pop();
        if (node != null) {
            System.out.print(node.data + " ");
            stack.push(node.right);
            stack.push(node.left);
        }
    }
}