> For the complete documentation index, see [llms.txt](https://stephanosterburg.gitbook.io/scrapbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://stephanosterburg.gitbook.io/scrapbook/coding/python/tra.md).

# Traverse A Tree

### Pre-order Traversal <a href="#pre-order-traversal" id="pre-order-traversal"></a>

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

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

**Example:**

```
Input: [1,null,2,3]
   1
    \
     2
    /
   3
​
Output: [1,2,3]
```

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
​
class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
    
        if root:
            # root.val
            # root.left
            # root.right
            return [root.val] + self.preorderTraversal(root.left) + 
                    self.preorderTraversal(root.right)
        else:
            return [] 
```

### In-order Traversal <a href="#in-order-traversal" id="in-order-traversal"></a>

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](https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/)).

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

#### Example:  <a href="#example" id="example"></a>

```
Input: [1,null,2,3]
   1
    \
     2
    /
   3
​
Output: [1,3,2]
```

```python
class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
    
        if root:
            # root.left 
            # root.val
            # root.right
            return self.inorderTraversal(root.left) + [root.val] + 
                    self.inorderTraversal(root.right)
        else:
            return [] 
```

### Post-order Traversal <a href="#post-order-traversal" id="post-order-traversal"></a>

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

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

**Example:**

```
Input: [1,null,2,3]
   1
    \
     2
    /
   3
​
Output: [3,2,1]
```

```python
class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
    
        if root:
            # root.left
            # root.right 
            # root.val
            return self.postorderTraversal(root.left) + 
                    self.postorderTraversal(root.right) + 
                    [root.val]
        else:
            return [] 
```

&#x20;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:

![](https://blobscdn.gitbook.com/v0/b/gitbook-28427.appspot.com/o/assets%2F-LLZ89zzVxrdnG1RG6CA%2F-LLZ8HfoV5Zor0rkUdAY%2F-LLZ9uLphq84-z8ESGRd%2Fmathematical_expression.png?alt=media\&token=82a88c97-a590-4a3e-b241-3074973c8310)

&#x20;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.

### Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:\
Given binary tree `[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

return its level order traversal as:

```
[
  [3],
  [9,20],
  [15,7]
]
```

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        
        # return empty if no root
        if not root:
            return result
        
        curr_level = [root]
        while curr_level:
            level_result = []
            next_level = []
            
            for curr in curr_level:
                level_result.append(curr.val)
                
                if curr.left:
                    next_level.append(curr.left)
                if curr.right:
                    next_level.append(curr.right)
                    
            result.append(level_result)
            
            curr_level = next_level
            
        return result
```