Binary Tree Traversal in Python (Pre/In/Post Order)

1 year ago
Olivia Parker
2 minutes

In Python, three tree traversal algorithms can be implemented using recursion: pre-order traversal, in-order traversal, and post-order traversal.

Here is a simple definition of a binary tree node class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Next, we can define three functions to implement algorithms for preorder traversal, inorder traversal, and postorder traversal.

  1. Preorder traversal: Firstly visit the root node, then recursively traverse the left subtree, and finally recursively traverse the right subtree.
def preorderTraversal(root):
    result = []
    if root:
        result.append(root.val)
        result += preorderTraversal(root.left)
        result += preorderTraversal(root.right)
    return result
  1. Inorder traversal: First recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree.
def inorderTraversal(root):
    result = []
    if root:
        result += inorderTraversal(root.left)
        result.append(root.val)
        result += inorderTraversal(root.right)
    return result
  1. Postorder traversal: recursively traverse the left subtree first, then recursively traverse the right subtree, and finally visit the root node.
def postorderTraversal(root):
    result = []
    if root:
        result += postorderTraversal(root.left)
        result += postorderTraversal(root.right)
        result.append(root.val)
    return result

Next, we can create a binary tree and use the above mentioned function to traverse it.

# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 前序遍历
print(preorderTraversal(root))  # Output: [1, 2, 4, 5, 3]

# 中序遍历
print(inorderTraversal(root))   # Output: [4, 2, 5, 1, 3]

# 后序遍历
print(postorderTraversal(root)) # Output: [4, 5, 2, 3, 1]

The above is the method for implementing three traversal algorithms for binary trees using Python.

bannerAds