Tree Traversals by Hand

Tree S1

Practice 1

Practice 2

Practice 3 (exam-like)

Tap to practice

This tree holds letters, placed like a BST in alphabetical order. Pick an order and tap the nodes in that order. If you miss twice, the next node glows. (Bonus: what do you notice about the in-order?)

Your coding task: pre-order with a stack

The next lesson writes all three orders in Java with recursion. You can already write pre-order with a tool you know: a stack. The stack holds the nodes that are still waiting for their turn.

Pre-order does N, then L, then R. When you pop a node, print it right away (N). Then its two children wait on the stack. A stack gives back the last item pushed, so push the right child first. Then the left child comes out first: L before R.

Finish preOrder in about 13 lines where it says YOUR CODE. Stack<TreeNode> works like Stack<Integer>, but each item is a node. main builds the starting BST with insert from the BST Insertion lesson. Run it: each printed line must match its comment.

 1import java.util.Stack;
 2
 3public class Main {
 4  // Prints the pre-order of the tree.
 5  // It uses a stack instead of recursion.
 6  static void preOrder(TreeNode root) {
 7    // YOUR CODE:
 8    // 1. Make a Stack<TreeNode>.
 9    // 2. If root is not null, push root. (An empty tree pushes
10    //    nothing, so the loop below never runs.)
11    // 3. While the stack is not empty:
12    //    a. Pop a node and print its data, then a space.  (N)
13    //    b. If it has a right child, push the right child.
14    //    c. If it has a left child, push the left child.
15    //    (Right goes in first, so left comes out first.)
16
17    System.out.println();
18  }
19
20  // Given: insert from the BST Insertion lesson.
21  static TreeNode insert(TreeNode root, int value) {
22    if (root == null) {
23      return new TreeNode(value);
24    }
25    TreeNode current = root;
26    while (true) {
27      if (value == current.data) {
28        return root;
29      } else if (value < current.data) {
30        if (current.left == null) {
31          current.left = new TreeNode(value);
32          return root;
33        }
34        current = current.left;
35      } else {
36        if (current.right == null) {
37          current.right = new TreeNode(value);
38          return root;
39        }
40        current = current.right;
41      }
42    }
43  }
44
45  public static void main(String[] args) {
46    int[] values = {40, 20, 60, 10, 30, 50, 70};
47    TreeNode root = null;
48    for (int i = 0; i < values.length; i++) {
49      root = insert(root, values[i]);
50    }
51    preOrder(root);   // expected: 40 20 10 30 60 50 70
52
53    root = insert(root, 45);
54    preOrder(root);   // expected: 40 20 10 30 60 50 45 70
55
56    TreeNode chain = null;
57    chain = insert(chain, 10);
58    chain = insert(chain, 20);
59    chain = insert(chain, 30);
60    preOrder(chain);  // expected: 10 20 30
61
62    preOrder(null);   // expected: (an empty line)
63  }
64}
65
66class TreeNode {
67  int data;
68  TreeNode left;
69  TreeNode right;
70
71  TreeNode(int value) {
72    data = value;
73    left = null;
74    right = null;
75  }
76}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

 1static void preOrder(TreeNode root) {
 2  Stack<TreeNode> stack = new Stack<>();
 3  if (root != null) {
 4    stack.push(root);
 5  }
 6  while (!stack.isEmpty()) {
 7    TreeNode node = stack.pop();
 8    System.out.print(node.data + " ");
 9    if (node.right != null) {
10      stack.push(node.right);
11    }
12    if (node.left != null) {
13      stack.push(node.left);
14    }
15  }
16  System.out.println();
17}