Flattening a Binary Tree I have this below Data Structure.



The output will be like 

m - n - o - p - q - r - s -t


Please review the below code and let me know if any optimization can be done.

public class Application {

    public static Node root = null;
    public static Node temp = root;
    public static Node anotherTemp;

    public static void main(String[] args) {

        Node m = new Node("m");
        Node n = new Node("n");
        Node o = new Node("o");
        Node p = new Node("p");
        m.setDown(n);
        n.setDown(o);
        o.setDown(p);

        Node q = new Node("q");
        Node r = new Node("r");
        Node s = new Node("s");

        m.setRight(q);
        q.setDown(r);
        r.setDown(s);

        Node t = new Node("t");
        q.setRight(t);
        root = new Node(m.getValue());
        temp = root;

        anotherTemp = m;

        flattern(m);
        // Here is my output
        System.out.println(temp);
    }

    public static void flattern(Node m) {

        if (m.getRight() == null)
            return;

        while (m.getDown() != null) {
            if (!m.getValue().equals("m")) {
                root.setRight(new Node(m.getValue()));
                m = m.getDown();
                root = root.getRight();
            }
            else
                m = m.getDown();
        }
        if (m.getDown() == null) {
            root.setRight(new Node(m.getValue()));
            if (anotherTemp.getRight() != null) {
                anotherTemp = anotherTemp.getRight();
                root.getRight().setRight(new Node(anotherTemp.getValue()));
                root = root.getRight();
            }
        }

        if (m.getDown() == null)
            flattern(anotherTemp);
        System.out.println(temp);
        System.out.println(root);
    }

}

class Node {
    String value;
    Node right;
    Node down;

    Node(String val) {
        this.value = val;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public Node getDown() {
        return down;
    }

    public void setDown(Node down) {
        this.down = down;
    }

}
Possible bug

If you were to set a right node to the node r with

r.setRight(new Node("v"));


the result would not contain this node.

OOP paradigm

There are several fundamental issues with your solution. Mainly, it breaks completely the OOP paradigm; this is shown by:


The use of static global variables:

public static Node root = null;
public static Node temp = root;
public static Node anotherTemp;


This is not a good idea: this creates variables that can be seen and modified by anyone, when in reality, they only make sense when flattening the nodes.
The flattening algorithm depends on the value itself!

if (!m.getValue().equals("m")) {


The issue with this line is that you have just made your algorithm dependent on your data. It cannot flatten any node since "m" is hard-coded. If tomorrow your first node has a value of "a", it will be broken.


In Object-Oriented Programming, you should give behaviour to objects. Your object in this case is a Node, and you are trying to flatten it. Therefore, it makes sense to have a method flatten() inside the class Node: any node can be flattened and it is the responsibility of a Node to be able to flatten itself.

Let's reason through what it means for a node n to be flattened:


The new right of node n will be the result of flatting what was below it.
After that, the right-most node of n will have at its right set to the flattened previous right of n.


This shows a simple recursive solution:

class Node {

    // ...

    public Node flatten() {
        Node node = new Node(value);
        Node prevRight = right;
        if (down != null) {
            node.setRight(down.flatten());
        }
        if (prevRight != null) {
            Node rightMost = node;
            while (rightMost.getRight() != null) {
                rightMost = rightMost.getRight();
            }
            rightMost.setRight(prevRight.flatten());
        }
        return node;
    }

}


Be careful of typos also, flattern is mis-spelled: it should be flatten.