> 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
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
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:
```
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
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 []
```
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:
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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## 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, and the optional `goal` query parameter:
```
GET https://stephanosterburg.gitbook.io/scrapbook/coding/python/tra.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
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.