Binary Tree Traversal


#tree
- 2 minutes read - 278 words

Traversal

Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree

  • In-order Traversal
  • Pre-order Traversal
  • Post-order Traversal
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

In-order Traversal

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.

def inorderTraversal(self, root: TreeNode) -> List[int]:
    order = []
    if root == None:
        return order
    
    order.extend(self.inorderTraversal(root.left))
    order.append(root.val)
    order.extend(self.inorderTraversal(root.right))
    
    return order

Pre-order Traversal

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

def preorderTraversal(self, root: TreeNode) -> List[int]:
    order = []
    if root == None:
        return order
    
    order.append(root.val)
    order.extend(self.preorderTraversal(root.left))
    order.extend(self.preorderTraversal(root.right))
    
    return order

Post-order Traversal

In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.

Recursive

def postorderTraversal(self, root: TreeNode) -> List[int]:
    order = []
    if root == None:
        return order
    
    order.extend(self.postorderTraversal(root.left))
    order.extend(self.postorderTraversal(root.right))
    order.append(root.val)

Iterative

def postorderTraversal(self, root: TreeNode) -> List[int]:
    order = []
    if root == None:
        return order

    stack = []
    stack.append(root)
    while len(stack) != 0:
        node = stack.pop()
        if node.left != None:
            stack.append(node.left)
        if node.right != None:
            stack.append(node.right)

        order.append(node)
    vals = []
    for i in range(len(order)-1, -1, -1):
        vals.append(order[i].val)
    return vals