Preorder traversal for Nary trees

Question

I'm still a beginner to Java. I've just learned about binary search trees and the idea of preorder traversals, and how you'd be able to use recursion to implement preorder traversal of a binary tree. Something like this:

Void preorder(node root){
if(root==null){//base case when node becomes null we stop recursive function
return ;}
System.out.print(root.data+" ");// printing the value of node as first time we visit
Preorder(root.left);// look at left side of tree ,once left side complete
Preorder(root.right);// start having a look at right side of that specific node
}

However, how could this same recursive model be implemented for a N ary tree? one in which the number of children per node isn't necessarily 2? cause then the .left and .right wouldn't be applicable, no? Please lmk if more code needs to be provided, thank you.

M A M A · Accepted Answer · 2021-04-07T19:35:01

Instead of having only two children, the tree can have n children. So you need to model the children as a list, e.g. an ArrayList:

class Node {
    String data;
    List<Node> children = new ArrayList<>();

    public void addChild(Node node) {
        this.children.add(node);
    }
    
}

Then iterate over the children in the preorder traversal:

void preorder(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(node.data + " ");
    for (Node child : node.children) {
        preorder(child);
    }
}

Preorder traversal for Nary trees

1 Answers