SoftwareInLevels

Understanding Tree Recursion — Level 2

Implementation details, traversal orders, common patterns, and code examples in Python, Java, and C++.

Author

Mr. Oz

Date

Read

8 mins

Level 2
Code structure visualization showing tree traversal patterns and recursive call sequences

Author

Mr. Oz

Date

Read

8 mins

Share

Twitter YouTube

Now that you understand the concept of tree recursion, let's dive into the implementation details. We'll explore different traversal orders, code patterns, and best practices for writing tree recursion in real code.

The TreeNode Structure

Before we write recursive functions, let's understand what we're working with:

# Python

class TreeNode:

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

self.val = val

self.left = left

self.right = right

Each node contains:

  • val: The data stored in this node
  • left: Reference to the left child (or None)
  • right: Reference to the right child (or None)

Traversal Orders: The Three Patterns

The order in which we process nodes matters. There are three main patterns:

Preorder

Process → Left → Right

Root before children

Inorder

Left → Process → Right

Root in the middle

Postorder

Left → Right → Process

Root after children

Key insight: The only difference is WHERE you process the current node relative to the recursive calls!

Common Tree Recursion Patterns

Most tree recursion problems fall into these categories:

1. Accumulation (Collecting Values)

def inorder_traversal(root, result=None):

if result is None:

result = []

if root:

inorder_traversal(root.left, result)

result.append(root.val) # Process

inorder_traversal(root.right, result)

return result

2. Calculation (Computing a Value)

def max_depth(root):

if not root:

return 0

left_depth = max_depth(root.left)

right_depth = max_depth(root.right)

return 1 + max(left_depth, right_depth)

3. Modification (Changing the Tree)

def invert_tree(root):

if not root:

return None

root.left, root.right = root.right, root.left

invert_tree(root.left)

invert_tree(root.right)

return root

Code Examples in Three Languages

Python: Invert Binary Tree

def invertTree(root):

if not root:

return None

root.left, root.right = root.right, root.left

invertTree(root.left)

invertTree(root.right)

return root

Java: Invert Binary Tree

public TreeNode invertTree(TreeNode root) {

if (root == null) return null;

TreeNode temp = root.left;

root.left = root.right;

root.right = temp;

invertTree(root.left);

invertTree(root.right);

return root;

}

C++: Invert Binary Tree

TreeNode* invertTree(TreeNode* root) {

if (root == nullptr) return nullptr;

swap(root->left, root->right);

invertTree(root->left);

invertTree(root->right);

return root;

}

Common Pitfalls to Avoid

  • Forgetting the base case: Always handle null/None/nullptr first, or you'll get null pointer errors.
  • Not returning values: In calculation patterns, make sure to return and use the recursive results.
  • Swapping order incorrectly: When modifying, swap BEFORE recursing, or you'll swap already-inverted children.
  • Ignoring return values: For accumulation patterns, remember to return the accumulator through the recursion.
  • Confusing traversal orders: Preorder, inorder, and postorder produce different results — know which one you need.

Professional Tips

  • Think locally: Only consider the current node and trust that recursion handles the subtrees correctly.
  • Use helper functions: For complex problems, use a helper that carries additional state (like depth, path, or accumulator).
  • Draw small examples: Trace through recursion with a 3-node tree to verify your logic.
  • Consider return values carefully: What does each recursive call return? How do you combine them?

Ready for advanced concepts?

Continue to Level 3 Back to Level 1

Key Takeaways

  • Three traversal orders: Preorder (root-first), Inorder (root-middle), Postorder (root-last)
  • Three main patterns: Accumulation, Calculation, Modification
  • The structure is always: Base case → Process current → Recurse on children → Combine/Return
  • Trust the recursion: Focus on the current node, let recursion handle the rest

All Levels