BinaryTree InOrder Traversal in JAVA

This is my iterative and recursive implementation of the InOrder traversal method on a BinaryTree data structure. InOrder traversal is a form of depth first traversal, so I will be using a the Stack data structure to keep a history of the visited TreeNode and backtrack once I have reached the end of a branch. The idea behind this algorithm is to visit all the nodes on the left subtree, the root, then all the nodes on the right subtree. This method simply prints all the data in the TreeNode. I will start with the TreeNode definition.

TreeNode Definition

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

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

Iterative

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

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

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

Recursive

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

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

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