BinaryTree PreOrder Traversal in JAVA

PreOrder traversal is very similar to in-order traversal in terms of code. The idea behind pre-order traversal is to do all the processing before visiting the left subtree and the right subtree. I will use the stack data structures to keep a history of the visited elements, and used that as a map to backtrack.

Setup

#       1
#      / \
#     9   8
#    / \   \
#   6   4   3
#  / \     /
# 2   7   5
#
# Print out: 1 9 6 2 7 4 8 3 5

TreeNode Definition

public static class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int d) {
        data = d;
        left = null;
        right = null;
    }
}

Time & Space

The time and space complexities for this algorithm are O(n) and O(log(n)) respectively. The time complexity is O(n) because I will need to visit all the elements to print them. The space complexity is O(log(n)) because the stack will have at most as many elements in it as the height of the tree.

Iterative

public static void printPreOrder(TreeNode root) {
    if (root == null) return;

    Stack<TreeNode> parents = new Stack<TreeNode>();
    TreeNode cur = root;
    parents.push(cur);

    while (!parents.isEmpty() || cur != null) {
        if (cur != null) {
            System.out.printf("%d ", cur.data);
            parents.push(cur);
            cur = cur.left;
        }
        else {
            TreeNode parent = parents.pop();
            cur = parent.right;
        }
    }
}

Recursive

public static void printPreOrder(TreeNode root) {
    if (root == null) return;

    System.out.printf("%d ", root.data);
    printInOrder(root.left);
    printInOrder(root.right);
}

This article is my 19th oldest. It is 262 words long, and it’s got 0 comments for now.