Code Templates

These templates provide reusable implementations for tree traversal algorithms. Use them as starting points for solving tree problems. For the underlying concepts, refer to the Concept Guide.

Tree Node Definition

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) {}
};

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

class TreeNode
  attr_accessor :val, :left, :right

  def initialize(val = 0, left = nil, right = nil)
    @val = val
    @left = left
    @right = right
  end
end

Inorder Traversal (Left, Root, Right)

Inorder traversal visits nodes in sorted order for Binary Search Trees. This template directly solves Binary Tree Inorder Traversal.

Recursive Implementation

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

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

        inorder(node.left);      // Visit left subtree
        result.push(node.val);   // Process current node
        inorder(node.right);     // Visit right subtree
    }

    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

        inorder(node.left)       # Visit left subtree
        result.append(node.val)  # Process current node
        inorder(node.right)      # Visit right subtree

    inorder(root)
    return result

import java.util.*;

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

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

    inorderHelper(node.left, result);   // Visit left subtree
    result.add(node.val);                // Process current node
    inorderHelper(node.right, result);  // Visit right subtree
}

#include <vector>

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

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

        inorderHelper(node->left, result);   // Visit left subtree
        result.push_back(node->val);         // Process current node
        inorderHelper(node->right, result);  // Visit right subtree
    }
};

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

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

        inorder(node.Left)              // Visit left subtree
        result = append(result, node.Val) // Process current node
        inorder(node.Right)             // Visit right subtree
    }

    inorder(root)
    return result
}

def inorder_traversal(root)
  result = []

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

    inorder.call(node.left)   # Visit left subtree
    result << node.val        # Process current node
    inorder.call(node.right)  # Visit right subtree
  }

  inorder.call(root)
  result
end

Iterative Implementation (Using Stack)

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

    while (current || stack.length) {
        // Go to the leftmost node
        while (current) {
            stack.push(current);
            current = current.left;
        }

        // Process node and move to right subtree
        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:
        # Go to the leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Process node and move to right subtree
        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<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        // Go to the leftmost node
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        // Process node and move to right subtree
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

#include <vector>
#include <stack>

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

    while (current || !stack.empty()) {
        // Go to the leftmost node
        while (current) {
            stack.push(current);
            current = current->left;
        }

        // Process node and move to right subtree
        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 {
        // Go to the leftmost node
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        // Process node and move to right subtree
        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?
    # Go to the leftmost node
    while current
      stack.push(current)
      current = current.left
    end

    # Process node and move to right subtree
    current = stack.pop
    result << current.val
    current = current.right
  end

  result
end

Level Order Traversal (BFS)

Level order traversal processes nodes level by level using a queue. This template directly solves Binary Tree Level Order Traversal.

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

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

    while (queue.length) {
        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:
        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

Code Breakdown

Key Variables

Variable	Purpose
`result`	Stores the traversal output
`stack`	Used in iterative DFS to track nodes to visit
`queue`	Used in BFS to process nodes level by level
`current`	Pointer to the currently processed node
`levelSize`	Number of nodes at the current level (BFS)

Visual: Iterative Inorder Traversal

  flowchart TD
    subgraph Init["Initialization"]
        I1[Create empty result array]
        I2[Create empty stack]
        I3[Set current = root]
    end

    subgraph Loop["Main Loop"]
        L1{current OR stack not empty?}
        L2["Push current to stack"]
        L3["Move left: current = current.left"]
        L4{current exists?}
        L5["Pop from stack"]
        L6["Add node.val to result"]
        L7["Move right: current = current.right"]
    end

    subgraph Return["Return"]
        R1[Return result array]
    end

    Init --> L1
    L1 -->|Yes| L4
    L4 -->|Yes| L2 --> L3 --> L4
    L4 -->|No| L5 --> L6 --> L7 --> L1
    L1 -->|No| R1

Variations

Preorder Traversal (Root, Left, Right)

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

    function preorder(node) {
        if (!node) return;
        result.push(node.val);   // Process current node first
        preorder(node.left);
        preorder(node.right);
    }

    preorder(root);
    return result;
}

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

    def preorder(node: Optional[TreeNode]) -> None:
        if not node:
            return
        result.append(node.val)  # Process current node first
        preorder(node.left)
        preorder(node.right)

    preorder(root)
    return result

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

private void preorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);                // Process current node first
    preorderHelper(node.left, result);
    preorderHelper(node.right, result);
}

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

void preorderHelper(TreeNode* node, std::vector<int>& result) {
    if (!node) return;
    result.push_back(node->val);         // Process current node first
    preorderHelper(node->left, result);
    preorderHelper(node->right, result);
}

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

    var preorder func(node *TreeNode)
    preorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        result = append(result, node.Val) // Process current node first
        preorder(node.Left)
        preorder(node.Right)
    }

    preorder(root)
    return result
}

def preorder_traversal(root)
  result = []

  preorder = ->(node) {
    return if node.nil?
    result << node.val         # Process current node first
    preorder.call(node.left)
    preorder.call(node.right)
  }

  preorder.call(root)
  result
end

Postorder Traversal (Left, Right, Root)

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

    function postorder(node) {
        if (!node) return;
        postorder(node.left);
        postorder(node.right);
        result.push(node.val);   // Process current node last
    }

    postorder(root);
    return result;
}

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

    def postorder(node: Optional[TreeNode]) -> None:
        if not node:
            return
        postorder(node.left)
        postorder(node.right)
        result.append(node.val)  # Process current node last

    postorder(root)
    return result

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

private void postorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorderHelper(node.left, result);
    postorderHelper(node.right, result);
    result.add(node.val);                // Process current node last
}

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

void postorderHelper(TreeNode* node, std::vector<int>& result) {
    if (!node) return;
    postorderHelper(node->left, result);
    postorderHelper(node->right, result);
    result.push_back(node->val);         // Process current node last
}

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

    var postorder func(node *TreeNode)
    postorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        postorder(node.Left)
        postorder(node.Right)
        result = append(result, node.Val) // Process current node last
    }

    postorder(root)
    return result
}

def postorder_traversal(root)
  result = []

  postorder = ->(node) {
    return if node.nil?
    postorder.call(node.left)
    postorder.call(node.right)
    result << node.val         # Process current node last
  }

  postorder.call(root)
  result
end

Practice

Ready to apply these templates? Head to the Practice Problems page to solve curated LeetCode problems using these traversal techniques.

Pro Tip: For BSTs, inorder traversal produces sorted values. This property is useful for validating BSTs and finding kth smallest elements.