Recursion of Level Order Traversal of N-ary tree

Question

I am currently working on N-ary trees and I stumbled upon Level Order Traversal. It seemed very easy on theory , not so difficult to run on code , but now I want to step it up and add recursion so I can wrap my head around it better. The things is I am now finding it very difficult to do so. There is my code for:

- The node class

    

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

/**
 * Implementation of a generic tree node containing the data and a list of children.
 *
 * @param <T> Generic type meant to implement reference types into the tree.
 */
public class Node<T> {
  private T data;
  private List<Node<T>> children;

  /**
   * Constructor that initializes the data and the list of children of the current node.
   *
   * @param data The value of the node.
   */
  public Node(T data) {
    this.data = data;
    children = new ArrayList<>();
  }

  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }

  public List<Node<T>> getChildren() {
    return children;
  }

  public void setChildren(List<Node<T>> children) {
    this.children = children;
  }
}






-The tree class


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/** Implementation of a generic n-ary tree. */
public class Tree<T> {
  private Node root;
  private List<Node<T>> nodes;
  /**
   * Constructor that initializes the root node of the tree.
   *
   * @param data The value of the root node.
   */
  public Tree(T data) {
    root = new Node<>(data);
  }

  public Node getRoot() {
    return root;
  }

  /**
   * Method that implements the Level Order Traversal algorithm. It's a left to right traverse where
   * each level of the tree is being printed out. First the root , then it's children and then each
   * child's children etc.
   *
   * @param root The root node of a tree.
   */
  public String levelOrderTraversal(Node root) {
    StringBuilder result = new StringBuilder();
    if (root == null) {
      return "";
    }
    result.append("\n");
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
      int queueSize = q.size();
      while (queueSize > 0) {
        Node node = q.peek();
        q.remove();
        result.append(node.getData().toString()).append(" ");
        for (int i = 0; i < node.getChildren().size(); i++) {
          q.add((Node) node.getChildren().get(i));
        }
        queueSize--;
      }
      result.append("\n");
    }
    return result.toString();
  }

  /**
   * This method serves to recursively move through and retrieve the nodes, so they can be printed
   * out to the user.
   *
   * @param root The root node of the tree.
   */
  private void walkThroughElements(Node root) {
    if (root == null) {
      return;
    }
    nodes.add(root);
    for (Object node : root.getChildren()) {
      walkThroughElements((Node) node);
    }
  }
  /**
   * Implementation of pre-order traversal of a generic tree. This traversal visit the root node
   * first , prints it , then visits the whole left sub-tree (the list of every child node), prints
   * every node and then traverses the right sub-tree , prints the nodes and ends the algorithm.
   *
   * @param root The root node of the tree.
   * @return The nodes of the tree as a string.
   */
  private String preOrderTraversal(Node<T> root) {
    nodes = new ArrayList<>();
    StringBuilder result = new StringBuilder();
    walkThroughElements(root);
    for (Node node : nodes) {
      result.append(node.getData()).append(" ");
    }
    result.setLength(result.length() - 1);
    return result.toString();
  }

  public String preOrderTraversal() {
    return preOrderTraversal(root);
  }
}

Is there an efficient way or does it even make sense to run this level order traversal method recursively?

This is the level order code after some changes

    public String levelOrderTraversal(Node root) {
    StringBuilder result = new StringBuilder();
    if (root == null) {
      return "";
    }
    result.append("\n");
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    collectNodes(root, root.getChildren());
    result.append(root.getData().toString()).append(" ");
    result.append("\n");
    return result.toString();
  }

It gives the error on the line where collectNodes is called.

This is what collectNodes() looks like.

    private void collectNodes(Node<T> node, List<Node<T>> nodes) {
    nodes.add(node);
    for (Object child : node.getChildren()) {
      collectNodes((Node) child, nodes);
    }
  }

Answer 1

The proper way is to do it in a lazy way

// assume not null Node::data (if so, wrap into Optional or similar)
static <T> Stream<T> levelOrderTraversal(Node<T> tree) {

    final List<Node<T>> fifo = new ArrayList<>();

    if(tree != null)
        fifo.add(tree);

    final Function<T, T> next = o -> {
        if(fifo.isEmpty())
            return null; // End Of Stream
        Node<T> x = fifo.remove(0);
        System.out.println("++++++ " + x.data);
        if(x.children != null)
            fifo.addAll(x.children);
        return x.data;
    };

    return Stream.iterate(null, next::apply).skip(1).takeWhile(Objects::nonNull);
}

for example

++++++ foo
foo
++++++ bar1
bar1
++++++ bar2
bar2
++++++ par11
par11
++++++ par12
par12
++++++ par21
par21
++++++ par22
par22
++++++ subA
subA
++++++ subB
subB

where you only mantain the intermediate traversing level (not the whole tree).

For example, if you log every node expansion and filter the tree, not all nodes are logged

    levelOrderTraversal(tree)
            .takeWhile(x -> !x.equals("bar2"))
            .forEach(System.out::println);

only expand the foo, bar1 and bar2 nodes

++++++ foo
foo
++++++ bar1
bar1
++++++ bar2

Answer 2

You can solve those iteration problems using iteration (e.g. via a stack) or recursion. Let's use a method that gathers nodes much like your walkThroughElements():

Depth-first

Recursion

//add the node and then go deeper
void collect(Node node, Collection<Node> nodes) {
  nodes.add(node);

  for(Node child : node.getChildren()) {
    collect(child, nodes);
  }
}

Iteration

class Level {
  final Node node;
  Iterator<Node> childItr;

  //constructor, setters, getters
}

void collect(Collection<Node> nodes) {
  Stack<Level> levels = new Stack<>();

  nodes.add(root);
  levels.push(new Level(root, root.getChildren().iterator()));

  while( !levels.isEmpty() ) {
    Level currentLevel = levels.peek();
    
    //remove the current level as it doesn't have any more children
    if( !currentLevel.childItr.hasNext() ) {
      levels.pop();
    } else {
      //get the next child and add it to the result
      Node child = currentLevel.childItr.next();
      nodes.add(child);

      //go down to the child's level
      levels.push(new Level(child, child.getChildren().iterator())
    }
  }
}

Breadth-first

Recursion

//add the children first (i.e. the entire level) and then go deeper
void collectChildren(Node node, Collection<Node> nodes) {      
  for(Node child : node.getChildren()) {
    nodes.add(child);
    collectChildren(child, nodes);
  }
}

//special case: root node
void collect(Collection<Node> nodes) {
   nodes.add(root);
   collectChildren(root, nodes);
}

Iteration

void collect(Collection<Node> nodes) {
  Queue<Node> nodesToProcess = new LinkedList<>();

  nodesToProcess.add(root);

  while( !nodesToProcess.isEmpty() ) {
    Node node = nodesToProcess.poll();

    nodes.add(node);

    nodesToProcess.addAll(node.getChildren());
  }
}

As you can see, recursion is easier on depth-first than breadth-first but easy to read anyway. Recursion will use the call stack to maintain state so it takes up (non-heap) memory and also has limits to its depth (depends on how much memory there is but the infamous StackOverflowException would tell you there's either a bug or the tree is too deep).

Iteration is easier with breadth first and requires additional constructs like a stack or a queue. It requires some heap memory for those constructs and may be faster due to some optimizations but in general I'd not bother about performance differences here as they should only manifest themselves for really large trees - and in that case recursion might hit the call stack limit already.

Answer 3

Using recursion typically will be slower than iteration and use more stack space as well.But Yes,this can also be solved using recursive way(DFS approach).

For your reference : https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33562/Java-1ms-DFS-recursive-solution-and-2ms-BFS-iterative-solution