Tree Traversal: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Tree Traversal: Complete Guide with Examples and Complexity

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here runs in

O(N)

time. Space is

O(H)

for the depth-first versions and

O(W)

for level-order, where H is the tree height and W is the width of the widest level.

TreeNode Definition

The solutions on this page and on the practice problems page assume this node class, which is the same one LeetCode provides in its editor.

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

Main Template: Recursive Inorder Traversal

This is the template to memorize first, because every depth-first traversal is this function with one line moved. Recurse left, process the node, recurse right. In a BST the output comes back sorted, which is the property that validation problems build on.

Use this for Binary Tree Inorder Traversal .

function inorderTraversal(root) {
    const result = [];

    function inorder(node) {
        if (!node) return;

        // The left subtree must finish before this node
        // so that smaller values appear first
        inorder(node.left);
        result.push(node.val);
        inorder(node.right);
    }

    inorder(root);
    return result;
}

from typing import List, Optional

def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
    result = []

    def inorder(node: Optional[TreeNode]) -> None:
        if not node:
            return

        # Process the left subtree, then this node, then
        # the right subtree. For a BST this yields values
        # in strictly increasing order.
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)

    inorder(root)
    return result

import java.util.*;

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

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

    // Left subtree, then the node itself, then the right
    // subtree. The null check at the top is the base case
    // that stops the recursion at every leaf.
    inorder(node.left, result);
    result.add(node.val);
    inorder(node.right, result);
}

#include <vector>

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        inorder(root, result);
        return result;
    }

private:
    void inorder(TreeNode* node, std::vector<int>& result) {
        if (!node) return;

        // The order of these three lines is the whole
        // pattern. Moving the push_back line changes
        // the traversal order.
        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
    }
};

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

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        // Left subtree first. For a BST the values come
        // back sorted, which is what validation relies on.
        inorder(node.Left)
        result = append(result, node.Val)
        inorder(node.Right)
    }

    inorder(root)
    return result
}

def inorder_traversal(root)
  result = []

  inorder = ->(node) {
    return if node.nil?

    inorder.call(node.left)
    result << node.val
    inorder.call(node.right)
  }

  inorder.call(root)
  result
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

Variable	Purpose
`node`	The subtree currently being processed. Null means the subtree is empty and the recursion stops.
`result`	Collects node values in visit order.
`stack`	In the iterative version, remembers ancestors whose right subtree is still pending.
`queue`	In level-order, holds the next level while the current one is processed.
`levelSize`	Snapshot of the queue length taken before a level starts, so levels never merge.

Visual Mechanism

    flowchart TD
    A["inorder(node)"] --> B{"node is null?"}
    B -->|Yes| R["Return"]
    B -->|No| L["inorder(node.left)"]
    L --> P["Process node.val"]
    P --> RT["inorder(node.right)"]
    RT --> D["Return"]

Critical Sections

The base case is the null check at the top. Without it the recursion never stops and the first leaf throws. With it, an empty tree and a single node both work with no special cases.

The order of the three lines is the entire pattern. The left subtree must finish before the node is processed, and the node must be processed before the right subtree starts. For a BST that ordering is what turns the walk into a sorted sequence.

The result list is shared across all calls. Each recursive call appends its node and returns, so the list grows in visit order without any explicit combining step.

Variations

1. Iterative Inorder (Explicit Stack)

Use this when the tree can be deep enough to overflow the call stack. The behavior is identical to the recursive version. The stack plays the role the call stack played, so the traversal order does not change.

function inorderTraversalIterative(root) {
    const result = [];
    const stack = [];
    let current = root;

    while (current || stack.length) {
        // Push every left child on the way down. The
        // stack remembers ancestors whose right subtree
        // still needs processing.
        while (current) {
            stack.push(current);
            current = current.left;
        }

        // The top of the stack is the next node in
        // inorder order. Process it and move right.
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }

    return result;
}

from typing import List, Optional

def inorder_traversal_iterative(root: Optional[TreeNode]) -> List[int]:
    result = []
    stack = []
    current = root

    while current or stack:
        # Descend to the leftmost node, remembering
        # each ancestor. They pop back in reverse
        # order, which is exactly the order inorder needs.
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

import java.util.*;

public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // Push the whole left spine. Popping it later
        // returns the ancestors in left-to-right order.
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

#include <vector>
#include <stack>

class Solution {
public:
    std::vector<int> inorderTraversalIterative(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> stack;
        TreeNode* current = root;

        while (current || !stack.empty()) {
            // Walk down the left edge and push every
            // node. The stack holds ancestors whose
            // right subtrees still have to be visited.
            while (current) {
                stack.push(current);
                current = current->left;
            }

            current = stack.top();
            stack.pop();
            result.push_back(current->val);
            current = current->right;
        }

        return result;
    }
};

func inorderTraversalIterative(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    current := root

    for current != nil || len(stack) > 0 {
        // Push the left spine onto the stack so the
        // ancestors pop back in the right order.
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, current.Val)
        current = current.Right
    }

    return result
}

def inorder_traversal_iterative(root)
  result = []
  stack = []
  current = root

  while current || !stack.empty?
    # Collect the left spine. The stack unwinds in
    # exactly the order inorder needs.
    while current
      stack.push(current)
      current = current.left
    end

    current = stack.pop
    result << current.val
    current = current.right
  end

  result
end

2. Level-Order Traversal (BFS)

Use this when the answer depends on depth. Printing levels, finding shortest paths, and anything else that must see the tree one level at a time all need it. A queue holds the current level, and a size snapshot keeps levels from merging.

Use this for Binary Tree Level Order Traversal .

function levelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length) {
        // Snapshot the size before the loop. Children
        // added during this level must wait for the next.
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
}

from typing import List, Optional
from collections import deque

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        # Only the nodes already in the queue belong to
        # this level. Children go to the back and are
        # processed on the next iteration.
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

import java.util.*;

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

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

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }

        result.add(currentLevel);
    }

    return result;
}

#include <vector>
#include <queue>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;

    std::queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
        int levelSize = queue.size();
        std::vector<int> currentLevel;

        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = queue.front();
            queue.pop();
            currentLevel.push_back(node->val);
            if (node->left) queue.push(node->left);
            if (node->right) queue.push(node->right);
        }

        result.push_back(currentLevel);
    }

    return result;
}

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

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            currentLevel = append(currentLevel, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, currentLevel)
    }

    return result
}

def level_order(root)
  return [] if root.nil?

  result = []
  queue = [root]

  until queue.empty?
    level_size = queue.length
    current_level = []

    level_size.times do
      node = queue.shift
      current_level << node.val
      queue << node.left if node.left
      queue << node.right if node.right
    end

    result << current_level
  end

  result
end

3. Preorder and Postorder

Both are the recursive skeleton with the process line moved. Preorder processes the node before its children, so the root of every subtree arrives first. That is what serialization and cloning rely on. Postorder processes children first, which is what height and path-sum calculations rely on, because the parent needs both subtree answers before it can compute its own.

function preorderTraversal(root) {
    const result = [];

    function preorder(node) {
        if (!node) return;

        // Root before children, so the root of every
        // subtree arrives first. Serialization and
        // cloning rely on that order.
        result.push(node.val);
        preorder(node.left);
        preorder(node.right);
    }

    preorder(root);
    return result;
}

function postorderTraversal(root) {
    const result = [];

    function postorder(node) {
        if (!node) return;

        // Children before root, because the parent can
        // only be processed once both subtree answers exist.
        postorder(node.left);
        postorder(node.right);
        result.push(node.val);
    }

    postorder(root);
    return result;
}

from typing import List, Optional

def preorder_traversal(root: Optional[TreeNode]) -> List[int]:
    result = []

    def preorder(node: Optional[TreeNode]) -> None:
        if not node:
            return

        # Root before children, so the root of every
        # subtree is available immediately. That makes
        # rebuilding or copying a tree straightforward.
        result.append(node.val)
        preorder(node.left)
        preorder(node.right)

    preorder(root)
    return result


def postorder_traversal(root: Optional[TreeNode]) -> List[int]:
    result = []

    def postorder(node: Optional[TreeNode]) -> None:
        if not node:
            return

        # Children before root, because the parent can
        # combine both subtree results only after they exist.
        postorder(node.left)
        postorder(node.right)
        result.append(node.val)

    postorder(root)
    return result

import java.util.*;

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorder(root, result);
    return result;
}

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

    // Process the node before descending so the root
    // of every subtree comes first in the output.
    result.add(node.val);
    preorder(node.left, result);
    preorder(node.right, result);
}

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorder(root, result);
    return result;
}

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

    // Both children finish before the node itself,
    // which lets the node combine their results.
    postorder(node.left, result);
    postorder(node.right, result);
    result.add(node.val);
}

#include <vector>

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;
        preorder(root, result);
        return result;
    }

    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> result;
        postorder(root, result);
        return result;
    }

private:
    void preorder(TreeNode* node, std::vector<int>& result) {
        if (!node) return;

        // Root first, which serialization and cloning need
        result.push_back(node->val);
        preorder(node->left, result);
        preorder(node->right, result);
    }

    void postorder(TreeNode* node, std::vector<int>& result) {
        if (!node) return;

        // Children first, so the node can combine their results
        postorder(node->left, result);
        postorder(node->right, result);
        result.push_back(node->val);
    }
};

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

    var preorder func(node *TreeNode)
    preorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        // Node before children. Serialization uses this
        // because the root of every subtree is known first.
        result = append(result, node.Val)
        preorder(node.Left)
        preorder(node.Right)
    }

    preorder(root)
    return result
}

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

    var postorder func(node *TreeNode)
    postorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        // Children before the node. Height and path-sum
        // problems need both subtree answers first.
        postorder(node.Left)
        postorder(node.Right)
        result = append(result, node.Val)
    }

    postorder(root)
    return result
}

def preorder_traversal(root)
  result = []

  preorder = ->(node) {
    return if node.nil?

    result << node.val
    preorder.call(node.left)
    preorder.call(node.right)
  }

  preorder.call(root)
  result
end

def postorder_traversal(root)
  result = []

  postorder = ->(node) {
    return if node.nil?

    postorder.call(node.left)
    postorder.call(node.right)
    result << node.val
  }

  postorder.call(root)
  result
end

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .