# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://stephanosterburg.gitbook.io/scrapbook/coding/python/tra.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.