AI Hints
DSA in Python · Lesson 62 of 132

Tree Traversals

Depth first.

⏱ 2 min read▶ Video at 1:13:01🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

To print, search, or count a tree, you need to visit every node. Depth first traversal goes as deep as it can down one branch, before coming back to try the next. And recursion makes it beautifully short.

Tree Traversals
From the video: Tree Traversals
  • Visit every node
  • Go deep first
  • Recursion makes it short

Three orders

There are three classic depth first orders, and they differ only in when we visit the node itself. Pre order visits the node first, then the left and right subtrees. In order visits left, then the node, then right. Post order visits both children first. Run it. Look at in order. For this kind of tree, it comes out sorted.

traversals.pypython
from tree import sample

def pre(n):  return [n.value] + pre(n.left) + pre(n.right) if n else []
def ino(n):  return ino(n.left) + [n.value] + ino(n.right) if n else []
def post(n): return post(n.left) + post(n.right) + [n.value] if n else []

root = sample()
print("pre: ", pre(root))
print("in:  ", ino(root))
print("post:", post(root))
Output
pre:  [8, 3, 1, 6, 4, 7, 10, 14, 13]
in:   [1, 3, 4, 6, 7, 8, 10, 13, 14]
post: [1, 4, 7, 6, 3, 13, 14, 10, 8]
Also uses tree.py
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def sample():
    return TreeNode(8,
        TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
        TreeNode(10, None, TreeNode(14, TreeNode(13))))

PICTURE = '        8\n      /   \\\n     3     10\n    / \\      \\\n   1   6      14\n      / \\    /\n     4   7  13'

When to use each

Pre order is good for copying a tree, because you create each parent before its children. In order gives sorted order for binary search trees. And post order is good for deleting, or adding up sizes, because children are handled before their parent. All three are O of N.

keyvalue
Pre ordercopy a tree
In ordersorted output
Post orderchildren before parent
CostO(n)

Summary

Pre order, in order, and post order differ only in when the node is visited. Each takes three lines of recursion. Next, visiting a tree level by level.

Key takeaways
  • Pre: node first
  • In: node in the middle
  • Post: node last
Next up: Level Order — breadth first