Binary Tree Traversals (Inorder, Preorder and Postorder)
2023-06-15 16:51:38

What is Binary Tree?

Each node of the tree has at most two children - a left and a right child.

Complete Binary Tree

All the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

Perfect Binary Tree

A binary tree of height h having the maximum number of nodes is a perfect binary tree.

Full Binary Tree

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children. It is also known as a proper binary tree.

Tree Traversal

Iterative Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static List<Integer> preorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<>();
if(root==null) return results;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
//when it comes to the last node, stack will be empty
while(!stack.empty()){
TreeNode cur = stack.pop();
results.add(cur.val);
if(cur.right!=null)
stack.push(cur.right);
if(cur.left!=null)
stack.push(cur.left);
}

return results;
}

Iterative Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
while(cur!=null || !stack.empty()){
//left
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
//root and right
if(!stack.empty()){
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}

Iterative Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//postorder traversal:-> right, left, root
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> res = new ArrayList<>();
TreeNode cur = root;
TreeNode prev = null;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
if(!stack.empty()){
cur = stack.pop();
if(cur.right!=null && prev!=cur.right){
stack.push(cur);
cur=cur.right;
}else{
res.add(cur.val);
prev=cur;
cur=null;
}
}
}
return res;
}
Prev
2023-06-15 16:51:38
Next