A tree is a frequently-used data structure to simulate a hierarchical tree structure.

Each node of the tree will have a root value and a list of references to other nodes which are called child nodes. From graph view, a tree can also be defined as a directed acyclic graph which has N nodes and N-1 edges.

A Binary Tree is one of the most typical tree structure. As the name suggests, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

By completing this card, you will be able to:

  1. Understand the concept of a tree and a binary tree;
  2. Be familiar with different traversal methods;
  3. Use recursion to solve binary-tree-related problems;

Traverse A Tree

In the introduction, we have gone through the concept of a tree and a binary tree.

In this chapter, we will focus on the traversal methods used in a binary tree. Understanding these traversal methods will definitely help you have a better understanding of the tree structure and have a solid foundation for the further study.

The goal of this chapter is to:

  1. Understand the difference between different tree traversal methods;
  2. Be able to solve preorder, inorder and postorder traversal recursively;
  3. Be able to solve preorder, inorder and postorder traversal iteratively;
  4. Be able to do level traversal using BFS.

Traverse a Tree - Introduction

Pre-order Traversal

Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree.

In-order Traversal

In-order traversal is to traverse the left subtree first. Then visit the root. Finally, traverse the right subtree.

Typically, for binary search tree, we can retrieve all the data in sorted order using in-order traversal. We will mention that again in another card(Introduction to Data Structure - Binary Search Tree).

Post-order Traversal

Post-order traversal is to traverse the left subtree first. Then traverse the right subtree. Finally, visit the root.

It is worth noting that when you delete nodes in a tree, deletion process will be in post-order. That is to say, when you delete a node, you will delete its left child and its right child before you delete the node itself.

Also, post-order is widely use in mathematical expression. It is easier to write a program to parse a post-order expression. Here is an example:

math

You can easily figure out the original expression using the inorder traversal. However, it is not easy for a program to handle this expression since you have to check the priorities of operations.

If you handle this tree in postorder, you can easily handle the expression using a stack. Each time when you meet a operator, you can just pop 2 elements from the stack, calculate the result and push the result back into the stack.

Recursive or Iterative

Try to practice the three different traversal methods in our after-article exercise. You might want to implement the methods recursively or iteratively. Implement both recursion and iteration solutions and compare the differences between them.

Question - Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

1
2
3
4
5
6
7
8
9
10
11
12
// Recursive Without Helper Function
// When a method is called, the Java Virtual Machine creates a stack frame that stores the parameters and local variables for that method.
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        result.add(root.val);
        result.addAll(preorderTraversal(root.left)); // Recursive 部分，优先访问左边
        result.addAll(preorderTraversal(root.right)); // 当一个节点的所有左边节点都访问完毕，开始访问右边
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Recursive With Helper Function
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preHelper(result, root);
        return result;
    }

    private void preHelper(List<Integer> result, TreeNode root) { // 使用 Helper Function 可以将 Recursive 部分单独分出
        if (root == null) return;
        result.add(root.val);
        preHelper(result, root.left); // Recursive 部分，优先访问左边
        preHelper(result, root.right); // 当一个节点的所有左边节点都访问完毕，开始访问右边
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Iterative
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        if (root == null) return result;
        toVisit.push(root);
        while (!toVisit.empty()) {
            TreeNode visiting = toVisit.pop();
            result.add(visiting.val); // 先将该节点的值加入结果
            // 加入栈中的节点实际上等于 Recursive 部分
            if (visiting.right != null) toVisit.push(visiting.right); // 再将该节点的右边推入栈，后访问
            if (visiting.left != null) toVisit.push(visiting.left); // 再将该节点的左边推入栈，先访问
        }
        return result;
    }
}

Question - Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

1
2
3
4
5
6
7
8
9
10
11
// Recursive Without Helper Function
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        result.addAll(inorderTraversal(root.left)); // Recursive 部分，优先访问左边
        result.add(root.val); // 左边访问完毕，再将该节点的值加入
        result.addAll(inorderTraversal(root.right)); // 最后访问右边
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Recursive With Helper Function
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inHelper(result, root);
        return result;
    }

    private void inHelper(List<Integer> result, TreeNode root) { // 使用 Helper Function 可以将 Recursive 部分单独分出
        if (root == null) return;
        inHelper(result, root.left); // Recursive 部分，优先访问左边
        result.add(root.val); // 左边访问完毕，再将该节点的值加入
        inHelper(result, root.right); // 最后访问右边
        return;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Iterative
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode visiting = root;
        while (!toVisit.empty() || visiting != null) {
            while (visiting != null) { // 将所有正在访问节点的左孩子加入栈，直到叶子节点
                toVisit.push(visiting);
                visiting = visiting.left;
            }
            visiting = toVisit.pop(); // 访问栈顶的节点（第一个是最左边的叶子结点，后续是它的父节点）
            result.add(visiting.val); // 将该节点加入结果中
            visiting = visiting.right; // 访问该节点的右边（第一次没有）
        }
        return result;
    }
}

Question - Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Iterative
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) return result;
        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        while (!toVisit.empty()) {
            TreeNode visiting = toVisit.pop();
            result.addFirst(visiting.val); // 将该节点的值最先加到结果的最前方
            if (visiting.left != null) toVisit.push(visiting.left); // 再将该节点的左边推入栈，最后访问，值会加到结果的最前方
            if (visiting.right != null) toVisit.push(visiting.right);  // 再将该节点的右边推入栈，先访问
        }
        return result;
    }
}