CS Interview Prep: Tree Traversal

Several interview questions are tree traversal questions in disguise.

Problems that can be solved with a…

Preorder traversal

• Given a mind map, print a structured document

Preorder Traversal

Algorithm

The algorithm for preorder is as follows:

• Print the root
• If there’s a left subtree, run this algorithm on that subtree
• If there’s no left subtree, then run this algorithm the right subtree

In mathematical terms, let v be the vertex, and visit mean print or process a node:

preOrder(v)
  visit(v)
  for each child w of v
    preorder (w)

Code

In Java:

public void preOrder2(TreeNode<E> root){
    System.out.print(root + " ");
    if (root.left != null) {
        preOrder2(root.left);
    } else if (root.right != null) {
        preOrder2(root.right);
    }
}

In Java, precisely:

protected void preOrder(TreeNode<E> root) {
    if (root == null) return;
    System.out.print(root.element + " ");
    preOrder(root.left);
    preOrder(root.right);
}