Quick Reference O(n) / O(h) DFS / O(w) BFS

void dfs(TreeNode node) {
    if (node == null) return;
    // preorder: process here
    dfs(node.left);
    // inorder: process here
    dfs(node.right);
    // postorder: process here
}
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null)  queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

func dfs(node *TreeNode) {
    if node == nil { return }
    // preorder: process here
    dfs(node.Left)
    // inorder: process here
    dfs(node.Right)
    // postorder: process here
}
func bfs(root *TreeNode) {
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil  { queue = append(queue, node.Left) }
        if node.Right != nil { queue = append(queue, node.Right) }
    }
}

def dfs(node):
    if not node:
        return
    # preorder: process here
    dfs(node.left)
    # inorder: process here
    dfs(node.right)
    # postorder: process here

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

fn dfs(node: Option<&Box<TreeNode>>) {
    let Some(n) = node else { return };
    // preorder: process here
    dfs(n.left.as_ref());
    // inorder: process here
    dfs(n.right.as_ref());
    // postorder: process here
}
fn bfs(root: &TreeNode) {
    let mut queue = VecDeque::from([root]);
    while let Some(node) = queue.pop_front() {
        if let Some(l) = &node.left  { queue.push_back(l); }
        if let Some(r) = &node.right { queue.push_back(r); }
    }
}

function dfs(node: TreeNode | null): void {
    if (!node) return;
    // preorder: process here
    dfs(node.left);
    // inorder: process here
    dfs(node.right);
    // postorder: process here
}
function bfs(root: TreeNode): void {
    const queue: TreeNode[] = [root];
    while (queue.length) {
        const node = queue.shift()!;
        if (node.left)  queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

Use when

Process all nodes in a tree
Level-order traversal needed
Path from root to leaf
Compare left and right subtrees

Watch out

Not handling null nodes
Confusing pre/in/post-order
Using DFS when BFS is needed (shortest path in tree)

Pattern

Tree Traversal

Master all four tree traversal orders and know when to use each one.

Step 01

What Is This Pattern?

A binary tree can be visited in four fundamental orders. Each order processes the root, left subtree, and right subtree in a different sequence. Understanding which to use is the key to solving most tree problems efficiently.

The Four Traversal Orders

Consider this binary tree. Each traversal visits the same 7 nodes, but in a different order:

PreOrder

Root, Left, Right

4 2 1 3 6 5 7

InOrder

Left, Root, Right

1 2 3 4 5 6 7

PostOrder

Left, Right, Root

1 3 2 5 7 6 4

LevelOrder

Top to bottom, left to right

4 2 6 1 3 5 7

💡

Key observation: InOrder traversal of a BST always gives nodes in sorted order. This is the single most important fact for BST problems.

Step 02

When to Use Which

Choosing the right traversal order is half the battle. Here is a quick reference for each:

PreOrder

Serialize / deserialize a tree
Copy / clone a tree
Path-from-root problems
Build expression prefix notation

InOrder

BST problems (gives sorted order!)
Kth smallest/largest element
Validate BST property
Convert BST to sorted list

PostOrder

Delete / free a tree
Calculate height or depth
Bottom-up aggregation
Evaluate expression trees

LevelOrder

Level-by-level processing
Shortest path in unweighted tree
Right/left side view
Connect nodes at same level

⚡

Rule of thumb: If you need information from children before processing a node, use PostOrder. If you need to process a node before its children, use PreOrder. If you need sorted access in a BST, use InOrder. If you need level information, use LevelOrder.

Step 03

PreOrder Traversal

Visit the root first, then recurse on the left subtree, then the right subtree. The root is always the first element in the output.

Recursive Implementation

void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;

    result.add(root.val);      // 1. Visit root
    preorder(root.left, result);  // 2. Traverse left
    preorder(root.right, result); // 3. Traverse right
}

func preorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    *result = append(*result, root.Val) // 1. Visit root
    preorder(root.Left, result)          // 2. Traverse left
    preorder(root.Right, result)         // 3. Traverse right
}

def preorder(root: TreeNode | None, result: list[int]) -> None:
    if root is None:
        return

    result.append(root.val)       # 1. Visit root
    preorder(root.left, result)   # 2. Traverse left
    preorder(root.right, result)  # 3. Traverse right

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn preorder(
        root: Option<Rc<RefCell<TreeNode>>>,
        result: &mut Vec<i32>,
    ) {
        if let Some(node) = root {
            let n = node.borrow();
            result.push(n.val);                          // 1. Visit root
            Solution::preorder(n.left.clone(), result);  // 2. Traverse left
            Solution::preorder(n.right.clone(), result); // 3. Traverse right
        }
    }
}

function preorder(root: TreeNode | null, result: number[]): void {
    if (root === null) return;

    result.push(root.val);       // 1. Visit root
    preorder(root.left, result);  // 2. Traverse left
    preorder(root.right, result); // 3. Traverse right
}

Call Stack Visualization

For the tree [4, 2, 6, 1, 3, 5, 7], the recursive calls unfold like this:

preorder(4)              // visit 4
  preorder(2)            // visit 2
    preorder(1)          // visit 1
      preorder(null)     // return
      preorder(null)     // return
    preorder(3)          // visit 3
      preorder(null)     // return
      preorder(null)     // return
  preorder(6)            // visit 6
    preorder(5)          // visit 5
      preorder(null)     // return
      preorder(null)     // return
    preorder(7)          // visit 7
      preorder(null)     // return
      preorder(null)     // return

// Output: 4 2 1 3 6 5 7

preorder(4)              // visit 4
  preorder(2)            // visit 2
    preorder(1)          // visit 1
      preorder(nil)      // return
      preorder(nil)      // return
    preorder(3)          // visit 3
      preorder(nil)      // return
      preorder(nil)      // return
  preorder(6)            // visit 6
    preorder(5)          // visit 5
      preorder(nil)      // return
      preorder(nil)      // return
    preorder(7)          // visit 7
      preorder(nil)      // return
      preorder(nil)      // return

// Output: 4 2 1 3 6 5 7

preorder(4)              # visit 4
  preorder(2)            # visit 2
    preorder(1)          # visit 1
      preorder(None)     # return
      preorder(None)     # return
    preorder(3)          # visit 3
      preorder(None)     # return
      preorder(None)     # return
  preorder(6)            # visit 6
    preorder(5)          # visit 5
      preorder(None)     # return
      preorder(None)     # return
    preorder(7)          # visit 7
      preorder(None)     # return
      preorder(None)     # return

# Output: 4 2 1 3 6 5 7

preorder(4)              // visit 4
  preorder(2)            // visit 2
    preorder(1)          // visit 1
      preorder(None)     // return
      preorder(None)     // return
    preorder(3)          // visit 3
      preorder(None)     // return
      preorder(None)     // return
  preorder(6)            // visit 6
    preorder(5)          // visit 5
      preorder(None)     // return
      preorder(None)     // return
    preorder(7)          // visit 7
      preorder(None)     // return
      preorder(None)     // return

// Output: 4 2 1 3 6 5 7

preorder(4)              // visit 4
  preorder(2)            // visit 2
    preorder(1)          // visit 1
      preorder(null)     // return
      preorder(null)     // return
    preorder(3)          // visit 3
      preorder(null)     // return
      preorder(null)     // return
  preorder(6)            // visit 6
    preorder(5)          // visit 5
      preorder(null)     // return
      preorder(null)     // return
    preorder(7)          // visit 7
      preorder(null)     // return
      preorder(null)     // return

// Output: 4 2 1 3 6 5 7

Step 04

InOrder Traversal

Recurse on the left subtree first, then visit the root, then the right subtree. For a BST, this produces elements in sorted ascending order.

Recursive Implementation

void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;

    inorder(root.left, result);   // 1. Traverse left
    result.add(root.val);       // 2. Visit root
    inorder(root.right, result);  // 3. Traverse right
}

func inorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    inorder(root.Left, result)            // 1. Traverse left
    *result = append(*result, root.Val)  // 2. Visit root
    inorder(root.Right, result)           // 3. Traverse right
}

def inorder(root: TreeNode | None, result: list[int]) -> None:
    if root is None:
        return

    inorder(root.left, result)   # 1. Traverse left
    result.append(root.val)      # 2. Visit root
    inorder(root.right, result)  # 3. Traverse right

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn inorder(
        root: Option<Rc<RefCell<TreeNode>>>,
        result: &mut Vec<i32>,
    ) {
        if let Some(node) = root {
            let n = node.borrow();
            Solution::inorder(n.left.clone(), result);  // 1. Traverse left
            result.push(n.val);                          // 2. Visit root
            Solution::inorder(n.right.clone(), result); // 3. Traverse right
        }
    }
}

function inorder(root: TreeNode | null, result: number[]): void {
    if (root === null) return;

    inorder(root.left, result);   // 1. Traverse left
    result.push(root.val);       // 2. Visit root
    inorder(root.right, result);  // 3. Traverse right
}

Why BST + InOrder = Sorted?

In a BST, every node in the left subtree is smaller and every node in the right subtree is larger. InOrder visits left first (all smaller values), then the node itself, then right (all larger values). This naturally produces sorted output:

1

→

2

→

3

→

4

→

5

→

6

→

7

Step 05

PostOrder Traversal

Recurse on both subtrees before visiting the root. The root is always the last element in the output. This is ideal for bottom-up computations like calculating tree height.

Recursive Implementation

void postorder(TreeNode root, List<Integer> result) {
    if (root == null) return;

    postorder(root.left, result);  // 1. Traverse left
    postorder(root.right, result); // 2. Traverse right
    result.add(root.val);       // 3. Visit root (last!)
}

func postorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }

    postorder(root.Left, result)            // 1. Traverse left
    postorder(root.Right, result)           // 2. Traverse right
    *result = append(*result, root.Val)    // 3. Visit root (last!)
}

def postorder(root: TreeNode | None, result: list[int]) -> None:
    if root is None:
        return

    postorder(root.left, result)  # 1. Traverse left
    postorder(root.right, result) # 2. Traverse right
    result.append(root.val)      # 3. Visit root (last!)

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn postorder(
        root: Option<Rc<RefCell<TreeNode>>>,
        result: &mut Vec<i32>,
    ) {
        if let Some(node) = root {
            let n = node.borrow();
            Solution::postorder(n.left.clone(), result);  // 1. Traverse left
            Solution::postorder(n.right.clone(), result); // 2. Traverse right
            result.push(n.val);                           // 3. Visit root (last!)
        }
    }
}

function postorder(root: TreeNode | null, result: number[]): void {
    if (root === null) return;

    postorder(root.left, result);  // 1. Traverse left
    postorder(root.right, result); // 2. Traverse right
    result.push(root.val);       // 3. Visit root (last!)
}

Classic Use: Computing Height

int height(TreeNode root) {
    if (root == null) return 0;

    int left  = height(root.left);   // get left height first
    int right = height(root.right);  // get right height first
    return Math.max(left, right) + 1; // then process root
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left  := height(root.Left)  // get left height first
    right := height(root.Right) // get right height first
    if left > right {
        return left + 1          // then process root
    }
    return right + 1
}

def height(root: TreeNode | None) -> int:
    if root is None:
        return 0

    left  = height(root.left)        # get left height first
    right = height(root.right)       # get right height first
    return max(left, right) + 1      # then process root

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn height(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let n = node.borrow();
                let left  = Solution::height(n.left.clone());  // get left height first
                let right = Solution::height(n.right.clone()); // get right height first
                left.max(right) + 1                             // then process root
            }
        }
    }
}

function height(root: TreeNode | null): number {
    if (root === null) return 0;

    const left  = height(root.left);   // get left height first
    const right = height(root.right);  // get right height first
    return Math.max(left, right) + 1; // then process root
}

You need the children's heights before you can compute the parent's height. That is the essence of PostOrder: bottom-up information flow.

Step 06

LevelOrder Traversal (BFS)

Process nodes level by level from top to bottom using a queue. Unlike the DFS-based orders above, LevelOrder uses BFS and is naturally iterative.

Implementation with Queue

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();       // nodes at this level
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        size := len(queue)      // nodes at this level
        level := []int{}

        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)

            if node.Left != nil  { queue = append(queue, node.Left) }
            if node.Right != nil { queue = append(queue, node.Right) }
        }
        result = append(result, level)
    }
    return result
}

from collections import deque

def level_order(root: TreeNode | None) -> list[list[int]]:
    result: list[list[int]] = []
    if root is None:
        return result

    queue = deque([root])

    while queue:
        size = len(queue)             # nodes at this level
        level: list[int] = []

        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)

            if node.left is not None:  queue.append(node.left)
            if node.right is not None: queue.append(node.right)
        result.append(level)
    return result

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        if root.is_none() { return result; }

        let mut queue = VecDeque::new();
        queue.push_back(root.unwrap());

        while !queue.is_empty() {
            let size = queue.len();     // nodes at this level
            let mut level = Vec::new();

            for _ in 0..size {
                let node = queue.pop_front().unwrap();
                let n = node.borrow();
                level.push(n.val);

                if let Some(l) = n.left.clone()  { queue.push_back(l); }
                if let Some(r) = n.right.clone() { queue.push_back(r); }
            }
            result.push(level);
        }
        result
    }
}

function levelOrder(root: TreeNode | null): number[][] {
    const result: number[][] = [];
    if (root === null) return result;

    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const size = queue.length;       // nodes at this level
        const level: number[] = [];

        for (let i = 0; i < size; i++) {
            const node = queue.shift()!;
            level.push(node.val);

            if (node.left !== null)  queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
}

💡

The size trick: Capturing queue.size() at the start of each iteration lets you process exactly one level at a time. Without this, you would not know where one level ends and the next begins.

Step 07

Iterative Implementations

Recursive solutions use the call stack implicitly. For iterative versions, we manage an explicit stack. Each traversal has a distinct stack strategy.

Iterative PreOrder

Push right child first, then left. Since a stack is LIFO, left gets processed before right.

List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);             // visit immediately
        if (node.right != null) stack.push(node.right); // right first!
        if (node.left != null)  stack.push(node.left);  // left on top
    }
    return result;
}

func preorderIterative(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }

    stack := []*TreeNode{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, node.Val)      // visit immediately
        if node.Right != nil { stack = append(stack, node.Right) } // right first!
        if node.Left != nil  { stack = append(stack, node.Left) }  // left on top
    }
    return result
}

def preorder_iterative(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    if root is None:
        return result

    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)             # visit immediately
        if node.right is not None: stack.append(node.right) # right first!
        if node.left is not None:  stack.append(node.left)  # left on top
    return result

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn preorder_iterative(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = Vec::new();
        if root.is_none() { return result; }

        let mut stack = Vec::new();
        stack.push(root.unwrap());

        while let Some(node) = stack.pop() {
            let n = node.borrow();
            result.push(n.val);                               // visit immediately
            if let Some(r) = n.right.clone() { stack.push(r); } // right first!
            if let Some(l) = n.left.clone()  { stack.push(l); } // left on top
        }
        result
    }
}

function preorderIterative(root: TreeNode | null): number[] {
    const result: number[] = [];
    if (root === null) return result;

    const stack: TreeNode[] = [root];

    while (stack.length > 0) {
        const node = stack.pop()!;
        result.push(node.val);             // visit immediately
        if (node.right !== null) stack.push(node.right); // right first!
        if (node.left !== null)  stack.push(node.left);  // left on top
    }
    return result;
}

Iterative InOrder

Go left as far as possible, pushing each node. When you cannot go left, pop and visit, then go right.

List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {           // go left as far as possible
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();              // visit
        result.add(curr.val);
        curr = curr.right;                // then go right
    }
    return result;
}

func inorderIterative(root *TreeNode) []int {
    result := []int{}
    stack  := []*TreeNode{}
    curr   := root

    for curr != nil || len(stack) > 0 {
        for curr != nil {              // go left as far as possible
            stack = append(stack, curr)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]   // visit
        stack = stack[:len(stack)-1]
        result = append(result, curr.Val)
        curr = curr.Right               // then go right
    }
    return result
}

def inorder_iterative(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    stack: list[TreeNode] = []
    curr = root

    while curr is not None or stack:
        while curr is not None:           # go left as far as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()              # visit
        result.append(curr.val)
        curr = curr.right                # then go right
    return result

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn inorder_iterative(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        let mut curr = root;

        while curr.is_some() || !stack.is_empty() {
            while let Some(node) = curr {   // go left as far as possible
                curr = node.borrow().left.clone();
                stack.push(node);
            }
            let node = stack.pop().unwrap(); // visit
            result.push(node.borrow().val);
            curr = node.borrow().right.clone(); // then go right
        }
        result
    }
}

function inorderIterative(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let curr = root;

    while (curr !== null || stack.length > 0) {
        while (curr !== null) {           // go left as far as possible
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop()!;             // visit
        result.push(curr.val);
        curr = curr.right;                // then go right
    }
    return result;
}

Iterative PostOrder

Use a modified preorder (root, right, left) and reverse the result. This avoids the complexity of tracking whether both children have been visited.

List<Integer> postorderIterative(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);        // add to FRONT (reverse)
        if (node.left != null)  stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return result;
}

func postorderIterative(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }

    stack := []*TreeNode{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append([]int{node.Val}, result...) // prepend (reverse)
        if node.Left != nil  { stack = append(stack, node.Left) }
        if node.Right != nil { stack = append(stack, node.Right) }
    }
    return result
}

from collections import deque

def postorder_iterative(root: TreeNode | None) -> list[int]:
    result: deque[int] = deque()
    if root is None:
        return list(result)

    stack = [root]

    while stack:
        node = stack.pop()
        result.appendleft(node.val)       # add to FRONT (reverse)
        if node.left is not None:  stack.append(node.left)
        if node.right is not None: stack.append(node.right)
    return list(result)

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn postorder_iterative(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result: VecDeque<i32> = VecDeque::new();
        if root.is_none() { return result.into_iter().collect(); }

        let mut stack = Vec::new();
        stack.push(root.unwrap());

        while let Some(node) = stack.pop() {
            let n = node.borrow();
            result.push_front(n.val);                        // prepend (reverse)
            if let Some(l) = n.left.clone()  { stack.push(l); }
            if let Some(r) = n.right.clone() { stack.push(r); }
        }
        result.into_iter().collect()
    }
}

function postorderIterative(root: TreeNode | null): number[] {
    const result: number[] = [];
    if (root === null) return result;

    const stack: TreeNode[] = [root];

    while (stack.length > 0) {
        const node = stack.pop()!;
        result.unshift(node.val);          // add to FRONT (reverse)
        if (node.left !== null)  stack.push(node.left);
        if (node.right !== null) stack.push(node.right);
    }
    return result;
}

⚡

PostOrder trick explained: Normal preorder is Root-Left-Right. If we swap to Root-Right-Left and reverse the result, we get Left-Right-Root, which is PostOrder. Using addFirst reverses as we go, avoiding a separate reverse step.

Step 08

Morris Traversal — O(1) Space

Both recursive and iterative approaches use O(h) space for the stack. Morris Traversal achieves O(1) space by temporarily modifying the tree structure using threaded binary trees.

The Core Idea

For each node, find its inorder predecessor (rightmost node in the left subtree). Create a temporary link from the predecessor back to the current node. This "thread" lets us return to the parent without a stack.

STEP 1: CREATE THREAD

If left child exists and no thread: find predecessor, link predecessor.right to current node, move left.

STEP 2: FOLLOW THREAD

If thread already exists: visit the node, remove the thread (restore tree), move right.

Morris InOrder

List<Integer> morrisInorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;

    while (curr != null) {
        if (curr.left == null) {
            result.add(curr.val);     // no left subtree, visit
            curr = curr.right;
        } else {
            // Find inorder predecessor
            TreeNode pred = curr.left;
            while (pred.right != null && pred.right != curr)
                pred = pred.right;

            if (pred.right == null) {
                pred.right = curr;    // create thread
                curr = curr.left;
            } else {
                pred.right = null;    // remove thread
                result.add(curr.val); // visit
                curr = curr.right;
            }
        }
    }
    return result;
}

func morrisInorder(root *TreeNode) []int {
    result := []int{}
    curr   := root

    for curr != nil {
        if curr.Left == nil {
            result = append(result, curr.Val) // no left subtree, visit
            curr = curr.Right
        } else {
            // Find inorder predecessor
            pred := curr.Left
            for pred.Right != nil && pred.Right != curr {
                pred = pred.Right
            }

            if pred.Right == nil {
                pred.Right = curr    // create thread
                curr = curr.Left
            } else {
                pred.Right = nil                        // remove thread
                result = append(result, curr.Val)      // visit
                curr = curr.Right
            }
        }
    }
    return result
}

def morris_inorder(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    curr = root

    while curr is not None:
        if curr.left is None:
            result.append(curr.val)     # no left subtree, visit
            curr = curr.right
        else:
            # Find inorder predecessor
            pred = curr.left
            while pred.right is not None and pred.right is not curr:
                pred = pred.right

            if pred.right is None:
                pred.right = curr      # create thread
                curr = curr.left
            else:
                pred.right = None      # remove thread
                result.append(curr.val) # visit
                curr = curr.right
    return result

// Morris Traversal modifies raw pointers; in Rust we use unsafe for O(1) space.
// This is the idiomatic safe approximation using a stack-free pointer walk.
impl Solution {
    pub fn morris_inorder(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut curr = root;

        while let Some(node) = curr.clone() {
            let left = node.borrow().left.clone();
            if left.is_none() {
                result.push(node.borrow().val);    // no left subtree, visit
                curr = node.borrow().right.clone();
            } else {
                // Find inorder predecessor
                let mut pred = left.unwrap();
                loop {
                    let next = pred.borrow().right.clone();
                    match next {
                        None => break,
                        Some(ref r) if Rc::ptr_eq(r, &node) => break,
                        Some(r) => { pred = r; }
                    }
                }
                if pred.borrow().right.is_none() {
                    pred.borrow_mut().right = Some(node.clone()); // create thread
                    curr = node.borrow().left.clone();
                } else {
                    pred.borrow_mut().right = None;               // remove thread
                    result.push(node.borrow().val);               // visit
                    curr = node.borrow().right.clone();
                }
            }
        }
        result
    }
}

function morrisInorder(root: TreeNode | null): number[] {
    const result: number[] = [];
    let curr = root;

    while (curr !== null) {
        if (curr.left === null) {
            result.push(curr.val);     // no left subtree, visit
            curr = curr.right;
        } else {
            // Find inorder predecessor
            let pred = curr.left;
            while (pred.right !== null && pred.right !== curr)
                pred = pred.right;

            if (pred.right === null) {
                pred.right = curr;    // create thread
                curr = curr.left;
            } else {
                pred.right = null;    // remove thread
                result.push(curr.val); // visit
                curr = curr.right;
            }
        }
    }
    return result;
}

📝

When to use Morris: Only when space is a hard constraint. The constant factor is higher than stack-based approaches, and the temporary tree modification makes it unsuitable for concurrent access. For interviews, knowing it exists and how it works is usually sufficient.

Step 09

Common Problems

These LeetCode problems directly test tree traversal patterns:

#94 Binary Tree Inorder Traversal

#144 Binary Tree Preorder Traversal

#145 Binary Tree Postorder Traversal

#102 Binary Tree Level Order Traversal

#230 Kth Smallest Element in a BST

#98 Validate Binary Search Tree

#297 Serialize and Deserialize Binary Tree

#104 Maximum Depth of Binary Tree

Step 10

Interactive Demo

Step through each traversal order on the binary tree below. Watch which node is visited and how the stack or queue changes at each step.

Tree Traversal Visualizer

Visit Order

Stack

Step 11

Complexity Analysis

Time

O(n)

Space (Recursive)

O(h)

Space (LevelOrder)

O(n)

Space (Morris)

O(1)

All traversals visit each node exactly once, giving O(n) time. For space: recursive and iterative stack-based traversals use O(h) where h is the tree height (O(log n) for balanced, O(n) for skewed). LevelOrder uses a queue that can hold up to O(n) nodes (the widest level). Morris Traversal achieves O(1) auxiliary space by threading the tree.

📝

h vs n: For a balanced binary tree, h = log(n). For a completely skewed tree (essentially a linked list), h = n. In interviews, stating O(h) shows you understand the distinction. For worst-case analysis, O(h) = O(n).