Binary Tree Traversals: DFS recursion Pattern

Learning Outcome

After this lesson, you should be able to explain inorder traversal and write a clean recursive DFS that visits every node once.

Problem Statement

Given the root of a binary tree, return the inorder traversal of its node values. Inorder means: visit left subtree, then current node, then right subtree.

Brute Force Approach

Store root-to-node paths or flatten the tree with a less precise traversal, then try to reorder values later.

This makes the problem harder than needed. Traversal order should be produced directly while visiting the tree.

Optimized Approach

Use DFS recursion. For each node, recursively process the left child, add the current value, then recursively process the right child.

Exact Pseudocode

answer = []
dfs(node):
  if node is null:
    return
  dfs(node.left)
  answer.add(node.val)
  dfs(node.right)
dfs(root)
return answer
  

Reference Code

class Solution:
    def inorderTraversal(self, root):
        answer = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            answer.append(node.val)
            dfs(node.right)

        dfs(root)
        return answer
  

Sample Dry Run

Complexity

Edge Cases

• Empty tree returns an empty list.
• Single-node tree returns that one value.
• Skewed tree may have recursion depth O(n).

Interview Checklist

• Remember inorder is left, root, right.
• Add the value between left and right recursion.
• State recursion stack space separately from output space.

FAQs