Tree Traversals (DFS)

DSA · Trees

Theory

Depth-first traversals visit nodes by going as deep as possible before backtracking. Pre-order visits root, left, right (useful for copying a tree). In-order visits left, root, right (gives sorted order in a BST). Post-order visits left, right, root (useful for deleting a tree or computing sizes bottom-up). Each visits every node once, so they take O(n) time and O(h) stack space for height h.

Why we use it

Traversals are how you read, search, copy, serialise and evaluate trees.

When to use it

Use pre-order to serialise or clone, in-order to get sorted output from a BST, post-order for bottom-up calculations such as folder sizes.

How it works

  1. visit(node)
  2. node is None? Yes: Return. No: Choose order.
  3. Preorder: node, left, right | Inorder: left, node, right | Postorder: left, right, node
  4. Recursion visits every node once: O(n)

Syntax

pre(n):  visit(n); pre(n.left); pre(n.right)
in(n):   in(n.left); visit(n); in(n.right)
post(n): post(n.left); post(n.right); visit(n)

Time: O(n)   Space: O(h)

Example

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

root = Node("F", Node("B", Node("A"), Node("D", Node("C"), Node("E"))), Node("G", None, Node("I", Node("H"))))

def pre(n, out):
    if n:
        out.append(n.val); pre(n.left, out); pre(n.right, out)
    return out

def ino(n, out):
    if n:
        ino(n.left, out); out.append(n.val); ino(n.right, out)
    return out

def post(n, out):
    if n:
        post(n.left, out); post(n.right, out); out.append(n.val)
    return out

print("Pre-order: ", " ".join(pre(root, [])))
print("In-order:  ", " ".join(ino(root, [])))
print("Post-order:", " ".join(post(root, [])))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic