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;
}

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.

StackExchange Code Review Q#135169, answer score: 5