Algorithm for Modified Preorder Tree Traversal in Java

Question

In the spirit of How to repair a corrupted MPTT tree (nested set) in the database using SQL?, I am trying to figure out an algorithm to determine the left and right values of a Modified Preorder Tree Traversal in Java given a root Node. Does anyone have any experience converting a regular pre order traversal into the modified traversal?

I currently have this as my preorder traversal.

List<Node> preorderTraversal(Node root) {
    List<Node> list = new ArrayList<>();
    if(root == null) return list;
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while(!stack.empty()) {
        root = stack.pop();
        list.add(root);

        if(root.children != null) {
            for(Node child : root.children) {
                if(child != null) {
                    stack.push(child);
                }
            }
        }
    }
    return list;
}

Answer 1

Firstly, your preorder traversal code traverses children in reverse order. When you push the children onto the stack in order, they get popped in reverse order, leading to incorrect behaviour. It should be something like this:

static List<Node> preorderTraversal(Node root) {
    List<Node> list = new ArrayList<>();
    if (root == null) return list;
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.empty()) {
        root = stack.pop();
        list.add(root);

        if (root.children != null) {
            // iterate in reverse
            for (int i = root.children.size() - 1; i >= 0; i--) {
                Node child = root.children.get(i);
                if (child != null) {
                    stack.push(child);
                }
            }
        }
    }
    return list;
}

Before we look at modified preorder traversal, it is helpful to look at how to implement preorder traversal recursively:

static List<Node> preorderTraversalRecursive(Node root) {
    ArrayList<Node> outList = new ArrayList<>();
    preorderTraversalRecursive(root, outList);
    return outList;
}

private static void preorderTraversalRecursive(Node root, ArrayList<Node> outList) {
    if (root == null) {
        return;
    }
    outList.add(root);

    if (root.children != null) {
        for (Node child : root.children) {
            preorderTraversalRecursive(child, outList);
        }
    }
}

This code simple outputs a node before traversing its children.

To make this into a modified preorder traversal, you only need to keep track of a counter that is incremented before and after every node is processed, and record it before and after the children are processed in order to get left and right values. Here, the current count is returned by the method so that it can be changed during processing of child nodes and this updated value used for their parents' right value:

static List<MPTTNode> modifiedPreorderTraversalRecursive(Node root) {
    ArrayList<MPTTNode> outList = new ArrayList<>();
    modifiedPreorderTraversalRecursive(root, 0, outList);
    return outList;
}

private static int modifiedPreorderTraversalRecursive(Node root, int counter, ArrayList<MPTTNode> outList) {
    if (root == null) {
        return counter;
    }
    counter++;
    MPTTNode mpttNode = new MPTTNode(root.data, counter, 0); // right value is unknown, leave as 0 for now
    outList.add(mpttNode);

    if (root.children != null) {
        for (Node child : root.children) {
            // modify counter
            counter = modifiedPreorderTraversalRecursive(child, counter, outList);
        }
    }
    counter++;

    mpttNode.right = counter;

    return counter;
}

This can also be implemented iteratively:

static List<MPTTNode> modifiedPreorderTraversal(Node root) {
    List<MPTTNode> list = new ArrayList<>();
    if (root == null) return list;
    Stack<Node> stack = new Stack<>();
    Stack<Integer> pending = new Stack<>();
    stack.push(root);

    int counter = 0;
    while (!stack.empty()) {
        root = stack.pop();
        if (root == null) {
            int nodeIndex = pending.pop();
            counter++;
            list.get(nodeIndex).right = counter;
            continue;
        }
        counter++;
        pending.push(list.size());
        list.add(new MPTTNode(root.data, counter, 0)); // right value is unknown, leave as 0 for now


        stack.push(null);
        if (root.children != null) {
            // iterate in reverse
            for (int i = root.children.size() - 1; i >= 0; i--) {
                Node child = root.children.get(i);
                if (child != null) {
                    stack.push(child);
                }
            }
        }
    }
    return list;
}

This works by using a pending stack to keep track of the indices of parent nodes within the output list (list). It uses null values in the stack stack to signal that all children of a node have been processed and so the right value of their parent is known.

---

Here's all my code, including the same example tree as is used in the linked question:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class Main {
    public static void main(String[] args) {
        Node tree = new Node("Electronics",
                Arrays.asList(
                        new Node("Televisions",
                                Arrays.asList(
                                        new Node("Tube"),
                                        new Node("LCD"),
                                        new Node("Plasma")
                                )
                        ),
                        new Node("Portable Electronics",
                                Arrays.asList(
                                        new Node("MP3 Players", Collections.singletonList(
                                                new Node("Flash")
                                        )),
                                        new Node("CD Players"),
                                        new Node("2 Way Radios")
                                )
                        )
                )
        );

        List<MPTTNode> list1 = Node.modifiedPreorderTraversal(tree);
        List<MPTTNode> list2 = Node.modifiedPreorderTraversalRecursive(tree);

        if (!list1.equals(list2)) {
            throw new RuntimeException("Traversals not equal");
        }

        for (var node : list1) {
            System.out.printf("%-30s left:%5d, right:%5d\n", node.data, node.left, node.right);
        }
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Node {
    String data;
    List<Node> children;

    public Node(String data, List<Node> children) {
        this.data = data;
        this.children = children;
    }

    public Node(String data) {
        this.data = data;
    }

    static List<Node> preorderTraversal(Node root) {
        List<Node> list = new ArrayList<>();
        if (root == null) return list;
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.empty()) {
            root = stack.pop();
            list.add(root);

            if (root.children != null) {
                // iterate in reverse
                for (int i = root.children.size() - 1; i >= 0; i--) {
                    Node child = root.children.get(i);
                    if (child != null) {
                        stack.push(child);
                    }
                }
            }
        }
        return list;
    }

    static List<MPTTNode> modifiedPreorderTraversal(Node root) {
        List<MPTTNode> list = new ArrayList<>();
        if (root == null) return list;
        Stack<Node> stack = new Stack<>();
        Stack<Integer> pending = new Stack<>();
        stack.push(root);

        int counter = 0;
        while (!stack.empty()) {
            root = stack.pop();
            if (root == null) {
                int nodeIndex = pending.pop();
                counter++;
                list.get(nodeIndex).right = counter;
                continue;
            }
            counter++;
            pending.push(list.size());
            list.add(new MPTTNode(root.data, counter, 0)); // right value is unknown, leave as 0 for now


            stack.push(null);
            if (root.children != null) {
                // iterate in reverse
                for (int i = root.children.size() - 1; i >= 0; i--) {
                    Node child = root.children.get(i);
                    if (child != null) {
                        stack.push(child);
                    }
                }
            }
        }
        return list;
    }

    static List<Node> preorderTraversalRecursive(Node root) {
        ArrayList<Node> outList = new ArrayList<>();
        preorderTraversalRecursive(root, outList);
        return outList;
    }

    private static void preorderTraversalRecursive(Node root, ArrayList<Node> outList) {
        if (root == null) {
            return;
        }
        outList.add(root);

        if (root.children != null) {
            for (Node child : root.children) {
                preorderTraversalRecursive(child, outList);
            }
        }
    }
    static List<MPTTNode> modifiedPreorderTraversalRecursive(Node root) {
        ArrayList<MPTTNode> outList = new ArrayList<>();
        modifiedPreorderTraversalRecursive(root, 0, outList);
        return outList;
    }

    private static int modifiedPreorderTraversalRecursive(Node root, int counter, ArrayList<MPTTNode> outList) {
        if (root == null) {
            return counter;
        }
        counter++;
        MPTTNode mpttNode = new MPTTNode(root.data, counter, 0);
        outList.add(mpttNode);

        if (root.children != null) {
            for (Node child : root.children) {
                counter = modifiedPreorderTraversalRecursive(child, counter, outList);
            }
        }
        counter++;

        mpttNode.right = counter;

        return counter;
    }
}

import java.util.Objects;

public class MPTTNode {
    String data;
    int left;
    int right;

    public MPTTNode(String data, int left, int right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MPTTNode mpttNode = (MPTTNode) o;
        return left == mpttNode.left && right == mpttNode.right && Objects.equals(data, mpttNode.data);
    }
}

Output:

Electronics                    left:    1, right:   20
Televisions                    left:    2, right:    9
Tube                           left:    3, right:    4
LCD                            left:    5, right:    6
Plasma                         left:    7, right:    8
Portable Electronics           left:   10, right:   19
MP3 Players                    left:   11, right:   14
Flash                          left:   12, right:   13
CD Players                     left:   15, right:   16
2 Way Radios                   left:   17, right:   18