Binary Tree Traversal, Part 1

outline:

  1. pre-order, post-order, in-order traversal of binary tree
  2. level-order traversal of binary tree

pre-order, post-order, in-order traversal of binary tree

pre-order:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preorder(root, res);
return res;
}

public void preorder(TreeNode node, List res) {
if (node != null) {
res.add(node.val);
preorder(node.left, res);
preorder(node.right, res);
}
}
}

post-order:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}

public void postorder(TreeNode node, List res) {
if (node != null) {
postorder(node.left, res);
postorder(node.right, res);
res.add(node.val);
}
}
}

in-order:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}

public void inorder(TreeNode node, List res) {
if (node != null) {
inorder(node.left, res);
res.add(node.val);
inorder(node.right, res);
}
}
}

level-order

recursive method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int level = 0;
if (root == null)
return res;
level_recur(root, res, level);
return res;
}

public void level_recur(TreeNode node, List<List<Integer>> res, int level) {
// add new level if necessary
if (res.size() == level)
res.add(new ArrayList<Integer>());
// add current value to corresponding level
res.get(level).add(node.val);
// recursion
if (node.left != null)
level_recur(node.left, res, level+1);
if (node.right != null)
level_recur(node.right, res, level+1);
}
}

iterative method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (root == null)
return res;
int level = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
res.add(new ArrayList<Integer>());
int level_len = queue.size();
for (int i = 0; i < level_len; i++) {
TreeNode cur = queue.remove();
res.get(level).add(cur.val);
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
level += 1;
}
return res;
}
}