By Frank Luo

The Tree Traversal Algorithms are used to traversal the tree including Binary Tree and N-ary Tree.

1. Binary Tree Traversal
1. N-ary Tree Traversal

# Binary Tree

## PreOrder

Algorithm Preorder(tree) 1. Visit the root; 2. Traverse the left subtree, i.e., call Preorder(left-subtree); 3. Traverse the right subtree, i.e., call Preorder(right-subtree).

### Recursive

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

### Iteration

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

## InOrder

Algorithm Inorder(tree)

1. Traverse the left subtree, i.e., call Inorder(left-subtree);
2. Visit the root;
3. Traverse the right subtree, i.e., call Inorder(right-subtree).

### Recursive

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

### Iteration

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

## PostOrder

Algorithm Postorder(tree) 1. Traverse the left subtree, i.e., call Postorder(left-subtree); 2. Traverse the right subtree, i.e., call Postorder(right-subtree); 3. Visit the root.

### Recursive

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

### Iteration

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

# N-ary Tree Traversal

## PreOrder

### Recursive

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

### Iteration

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

## PostOrder

### Recursive

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

### Iteration

#### Analysis

• Time Complexity: $$O(n)$$
• Space Complexity: $$O(n)$$

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗