Binary Trees

from collections import deque


class TreeNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.left: TreeNode | None = None
        self.right: TreeNode | None = None


def build_tree(values: list[int | None]) -> TreeNode | None:
    """Builds a tree from level-order values, where None marks a missing child.
    This is how LeetCode writes trees down."""
    first = values[0] if values else None
    if first is None:
        return None
    root = TreeNode(first)
    queue = deque([root])
    i = 1
    # Hand out the remaining values two at a time, left child then right, to
    # the nodes in the order they were created.
    while i < len(values):
        node = queue.popleft()
        left = values[i]
        if left is not None:
            node.left = TreeNode(left)
            queue.append(node.left)
        i += 1
        right = values[i] if i < len(values) else None
        if right is not None:
            node.right = TreeNode(right)
            queue.append(node.right)
        i += 1
    return root


def preorder(node: TreeNode | None, result: list[int]) -> list[int]:
    """Node, then left subtree, then right subtree."""
    if node is None:
        return result
    result.append(node.val)  # Visit the node before either subtree.
    preorder(node.left, result)
    preorder(node.right, result)
    return result


def preorder_iterative(root: TreeNode | None) -> list[int]:
    """Preorder with your own stack in place of the call stack."""
    result: list[int] = []
    stack = [root] if root is not None else []
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push the right child first, so the left one comes off the stack first.
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)
    return result


def inorder(node: TreeNode | None, result: list[int]) -> list[int]:
    """Left subtree, then node, then right subtree."""
    if node is None:
        return result
    inorder(node.left, result)
    result.append(node.val)  # Visit the node between its subtrees.
    inorder(node.right, result)
    return result


def inorder_iterative(root: TreeNode | None) -> list[int]:
    """Inorder with your own stack, where each node waits while its left
    subtree is walked."""
    result: list[int] = []
    stack: list[TreeNode] = []
    node = root
    while node is not None or stack:
        # Go left as far as possible, pushing each node on the way down.
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        result.append(node.val)  # Its left subtree is done, so visit it.
        node = node.right  # Then walk its right subtree the same way.
    return result


def postorder(node: TreeNode | None, result: list[int]) -> list[int]:
    """Left subtree, then right subtree, then node."""
    if node is None:
        return result
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)  # Visit the node after both subtrees.
    return result


def postorder_iterative(root: TreeNode | None) -> list[int]:
    """Postorder with your own stack, where each node waits until both of its
    subtrees are done, just as its recursive call would."""
    result: list[int] = []
    stack: list[TreeNode] = []
    node = root
    last: TreeNode | None = None  # The node visited most recently.
    while node is not None or stack:
        # Go left as far as possible, pushing each node on the way down.
        while node is not None:
            stack.append(node)
            node = node.left
        top = stack[-1]
        # A subtree's root is the last node postorder visits in it, so if the
        # right child was just visited, the right subtree is done.
        if top.right is not None and top.right is not last:
            node = top.right  # Walk the right subtree before visiting top.
        else:
            result.append(top.val)  # Both subtrees are done, so visit it.
            last = stack.pop()
    return result


def level_order(root: TreeNode | None) -> list[list[int]]:
    """Values level by level: top to bottom, and left to right within a level."""
    levels: list[list[int]] = []
    queue = deque([root] if root is not None else [])
    while queue:
        # The nodes waiting in the queue right now make up exactly one level.
        size = len(queue)
        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)
        levels.append(level)
    return levels


if __name__ == "__main__":
    root = build_tree([1, 2, 3, 4, 5, None, 6])
    print(preorder(root, []))  # [1, 2, 4, 5, 3, 6]
    print(preorder_iterative(root))  # [1, 2, 4, 5, 3, 6]
    print(inorder(root, []))  # [4, 2, 5, 1, 3, 6]
    print(inorder_iterative(root))  # [4, 2, 5, 1, 3, 6]
    print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]
    print(postorder_iterative(root))  # [4, 5, 2, 6, 3, 1]
    print(level_order(root))  # [[1], [2, 3], [4, 5, 6]]
    print(level_order(build_tree([])))  # []

class TreeNode {
  val: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

// Builds a tree from level-order values, where null marks a missing child.
// This is how LeetCode writes trees down.
function buildTree(values: (number | null)[]): TreeNode | null {
  const first = values.length > 0 ? values[0] : null;
  if (first === null) return null;
  const root = new TreeNode(first);
  const queue = [root];
  let head = 0; // Reading from a head index keeps each dequeue O(1).
  let i = 1;
  // Hand out the remaining values two at a time, left child then right, to
  // the nodes in the order they were created.
  while (i < values.length) {
    const node = queue[head++];
    const left = values[i];
    if (left !== null) {
      node.left = new TreeNode(left);
      queue.push(node.left);
    }
    i++;
    const right = i < values.length ? values[i] : null;
    if (right !== null) {
      node.right = new TreeNode(right);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

// Node, then left subtree, then right subtree.
export function preorder(node: TreeNode | null, result: number[]): number[] {
  if (node === null) return result;
  result.push(node.val); // Visit the node before either subtree.
  preorder(node.left, result);
  preorder(node.right, result);
  return result;
}

// Preorder with your own stack in place of the call stack.
export function preorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack = root === null ? [] : [root];
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    // Push the right child first, so the left one comes off the stack first.
    if (node.right !== null) stack.push(node.right);
    if (node.left !== null) stack.push(node.left);
  }
  return result;
}

// Left subtree, then node, then right subtree.
export function inorder(node: TreeNode | null, result: number[]): number[] {
  if (node === null) return result;
  inorder(node.left, result);
  result.push(node.val); // Visit the node between its subtrees.
  inorder(node.right, result);
  return result;
}

// Inorder with your own stack, where each node waits while its left subtree
// is walked.
export function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    // Go left as far as possible, pushing each node on the way down.
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    result.push(node.val); // Its left subtree is done, so visit it.
    node = node.right; // Then walk its right subtree the same way.
  }
  return result;
}

// Left subtree, then right subtree, then node.
export function postorder(node: TreeNode | null, result: number[]): number[] {
  if (node === null) return result;
  postorder(node.left, result);
  postorder(node.right, result);
  result.push(node.val); // Visit the node after both subtrees.
  return result;
}

// Postorder with your own stack, where each node waits until both of its
// subtrees are done, just as its recursive call would.
export function postorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let node = root;
  let last: TreeNode | null = null; // The node visited most recently.
  while (node !== null || stack.length > 0) {
    // Go left as far as possible, pushing each node on the way down.
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    const top = stack[stack.length - 1];
    // A subtree's root is the last node postorder visits in it, so if the
    // right child was just visited, the right subtree is done.
    if (top.right !== null && top.right !== last) {
      node = top.right; // Walk the right subtree before visiting top.
    } else {
      result.push(top.val); // Both subtrees are done, so visit it.
      last = stack.pop()!;
    }
  }
  return result;
}

// Values level by level: top to bottom, and left to right within a level.
export function levelOrder(root: TreeNode | null): number[][] {
  const levels: number[][] = [];
  const queue = root === null ? [] : [root];
  let head = 0;
  while (head < queue.length) {
    // The nodes waiting in the queue right now make up exactly one level.
    const size = queue.length - head;
    const level: number[] = [];
    for (let k = 0; k < size; k++) {
      const node = queue[head++];
      level.push(node.val);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
    levels.push(level);
  }
  return levels;
}

const root = buildTree([1, 2, 3, 4, 5, null, 6]);
console.log(JSON.stringify(preorder(root, []))); // [1,2,4,5,3,6]
console.log(JSON.stringify(preorderIterative(root))); // [1,2,4,5,3,6]
console.log(JSON.stringify(inorder(root, []))); // [4,2,5,1,3,6]
console.log(JSON.stringify(inorderIterative(root))); // [4,2,5,1,3,6]
console.log(JSON.stringify(postorder(root, []))); // [4,5,2,6,3,1]
console.log(JSON.stringify(postorderIterative(root))); // [4,5,2,6,3,1]
console.log(JSON.stringify(levelOrder(root))); // [[1],[2,3],[4,5,6]]
console.log(JSON.stringify(levelOrder(buildTree([])))); // []

package main

import "fmt"

// TreeNode is one node of a binary tree.
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// buildTree builds a tree from level-order values, where nil marks a missing
// child. This is how LeetCode writes trees down.
func buildTree(values []any) *TreeNode {
	if len(values) == 0 || values[0] == nil {
		return nil
	}
	root := &TreeNode{Val: values[0].(int)}
	queue := []*TreeNode{root}
	i := 1
	// Hand out the remaining values two at a time, left child then right, to
	// the nodes in the order they were created.
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]
		if values[i] != nil {
			node.Left = &TreeNode{Val: values[i].(int)}
			queue = append(queue, node.Left)
		}
		i++
		if i < len(values) && values[i] != nil {
			node.Right = &TreeNode{Val: values[i].(int)}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// preorder appends values in node, left subtree, right subtree order.
func preorder(node *TreeNode, result []int) []int {
	if node == nil {
		return result
	}
	result = append(result, node.Val) // Visit the node before either subtree.
	result = preorder(node.Left, result)
	result = preorder(node.Right, result)
	return result
}

// preorderIterative returns the preorder values using your own stack in place
// of the call stack.
func preorderIterative(root *TreeNode) []int {
	result := []int{}
	stack := []*TreeNode{}
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, node.Val)
		// Push the right child first, so the left one comes off the stack first.
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return result
}

// inorder appends values in left subtree, node, right subtree order.
func inorder(node *TreeNode, result []int) []int {
	if node == nil {
		return result
	}
	result = inorder(node.Left, result)
	result = append(result, node.Val) // Visit the node between its subtrees.
	result = inorder(node.Right, result)
	return result
}

// inorderIterative returns the inorder values using your own stack, where each
// node waits while its left subtree is walked.
func inorderIterative(root *TreeNode) []int {
	result := []int{}
	stack := []*TreeNode{}
	node := root
	for node != nil || len(stack) > 0 {
		// Go left as far as possible, pushing each node on the way down.
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, node.Val) // Its left subtree is done, so visit it.
		node = node.Right                 // Then walk its right subtree the same way.
	}
	return result
}

// postorder appends values in left subtree, right subtree, node order.
func postorder(node *TreeNode, result []int) []int {
	if node == nil {
		return result
	}
	result = postorder(node.Left, result)
	result = postorder(node.Right, result)
	result = append(result, node.Val) // Visit the node after both subtrees.
	return result
}

// postorderIterative returns the postorder values using your own stack, where
// each node waits until both of its subtrees are done, just as its recursive
// call would.
func postorderIterative(root *TreeNode) []int {
	result := []int{}
	stack := []*TreeNode{}
	node := root
	var last *TreeNode // The node visited most recently.
	for node != nil || len(stack) > 0 {
		// Go left as far as possible, pushing each node on the way down.
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		top := stack[len(stack)-1]
		// A subtree's root is the last node postorder visits in it, so if the
		// right child was just visited, the right subtree is done.
		if top.Right != nil && top.Right != last {
			node = top.Right // Walk the right subtree before visiting top.
		} else {
			result = append(result, top.Val) // Both subtrees are done, so visit it.
			last = top
			stack = stack[:len(stack)-1]
		}
	}
	return result
}

// levelOrder returns the values level by level: top to bottom, and left to
// right within a level.
func levelOrder(root *TreeNode) [][]int {
	levels := [][]int{}
	queue := []*TreeNode{}
	if root != nil {
		queue = append(queue, root)
	}
	for len(queue) > 0 {
		// The nodes waiting in the queue right now make up exactly one level.
		size := len(queue)
		level := []int{}
		for k := 0; k < size; k++ {
			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)
			}
		}
		levels = append(levels, level)
	}
	return levels
}

func main() {
	root := buildTree([]any{1, 2, 3, 4, 5, nil, 6})
	fmt.Println(preorder(root, []int{}))        // [1 2 4 5 3 6]
	fmt.Println(preorderIterative(root))        // [1 2 4 5 3 6]
	fmt.Println(inorder(root, []int{}))         // [4 2 5 1 3 6]
	fmt.Println(inorderIterative(root))         // [4 2 5 1 3 6]
	fmt.Println(postorder(root, []int{}))       // [4 5 2 6 3 1]
	fmt.Println(postorderIterative(root))       // [4 5 2 6 3 1]
	fmt.Println(levelOrder(root))               // [[1] [2 3] [4 5 6]]
	fmt.Println(levelOrder(buildTree([]any{}))) // []
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public class TreeNode
    {
        public int Val;
        public TreeNode? Left, Right;

        public TreeNode(int val) => Val = val;
    }

    // Builds a tree from level-order values, where null marks a missing child.
    // This is how LeetCode writes trees down.
    static TreeNode? BuildTree(int?[] values)
    {
        if (values.Length == 0 || values[0] is not int first) return null;
        var root = new TreeNode(first);
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int i = 1;
        // Hand out the remaining values two at a time, left child then right, to
        // the nodes in the order they were created.
        while (i < values.Length)
        {
            var node = queue.Dequeue();
            if (values[i] is int left)
            {
                node.Left = new TreeNode(left);
                queue.Enqueue(node.Left);
            }
            i++;
            if (i < values.Length && values[i] is int right)
            {
                node.Right = new TreeNode(right);
                queue.Enqueue(node.Right);
            }
            i++;
        }
        return root;
    }

    // Node, then left subtree, then right subtree.
    public static List<int> Preorder(TreeNode? node, List<int> result)
    {
        if (node == null) return result;
        result.Add(node.Val); // Visit the node before either subtree.
        Preorder(node.Left, result);
        Preorder(node.Right, result);
        return result;
    }

    // Preorder with your own stack in place of the call stack.
    public static List<int> PreorderIterative(TreeNode? root)
    {
        var result = new List<int>();
        var stack = new Stack<TreeNode>();
        if (root != null) stack.Push(root);
        while (stack.Count > 0)
        {
            var node = stack.Pop();
            result.Add(node.Val);
            // Push the right child first, so the left one comes off the stack first.
            if (node.Right != null) stack.Push(node.Right);
            if (node.Left != null) stack.Push(node.Left);
        }
        return result;
    }

    // Left subtree, then node, then right subtree.
    public static List<int> Inorder(TreeNode? node, List<int> result)
    {
        if (node == null) return result;
        Inorder(node.Left, result);
        result.Add(node.Val); // Visit the node between its subtrees.
        Inorder(node.Right, result);
        return result;
    }

    // Inorder with your own stack, where each node waits while its left subtree
    // is walked.
    public static List<int> InorderIterative(TreeNode? root)
    {
        var result = new List<int>();
        var stack = new Stack<TreeNode>();
        var node = root;
        while (node != null || stack.Count > 0)
        {
            // Go left as far as possible, pushing each node on the way down.
            while (node != null)
            {
                stack.Push(node);
                node = node.Left;
            }
            node = stack.Pop();
            result.Add(node.Val); // Its left subtree is done, so visit it.
            node = node.Right; // Then walk its right subtree the same way.
        }
        return result;
    }

    // Left subtree, then right subtree, then node.
    public static List<int> Postorder(TreeNode? node, List<int> result)
    {
        if (node == null) return result;
        Postorder(node.Left, result);
        Postorder(node.Right, result);
        result.Add(node.Val); // Visit the node after both subtrees.
        return result;
    }

    // Postorder with your own stack, where each node waits until both of its
    // subtrees are done, just as its recursive call would.
    public static List<int> PostorderIterative(TreeNode? root)
    {
        var result = new List<int>();
        var stack = new Stack<TreeNode>();
        var node = root;
        TreeNode? last = null; // The node visited most recently.
        while (node != null || stack.Count > 0)
        {
            // Go left as far as possible, pushing each node on the way down.
            while (node != null)
            {
                stack.Push(node);
                node = node.Left;
            }
            var top = stack.Peek();
            // A subtree's root is the last node postorder visits in it, so if the
            // right child was just visited, the right subtree is done.
            if (top.Right != null && top.Right != last)
            {
                node = top.Right; // Walk the right subtree before visiting top.
            }
            else
            {
                result.Add(top.Val); // Both subtrees are done, so visit it.
                last = stack.Pop();
            }
        }
        return result;
    }

    // Values level by level: top to bottom, and left to right within a level.
    public static List<List<int>> LevelOrder(TreeNode? root)
    {
        var levels = new List<List<int>>();
        var queue = new Queue<TreeNode>();
        if (root != null) queue.Enqueue(root);
        while (queue.Count > 0)
        {
            // The nodes waiting in the queue right now make up exactly one level.
            int size = queue.Count;
            var level = new List<int>();
            for (int k = 0; k < size; k++)
            {
                var node = queue.Dequeue();
                level.Add(node.Val);
                if (node.Left != null) queue.Enqueue(node.Left);
                if (node.Right != null) queue.Enqueue(node.Right);
            }
            levels.Add(level);
        }
        return levels;
    }

    public static void Main()
    {
        var root = BuildTree(new int?[] { 1, 2, 3, 4, 5, null, 6 });
        Console.WriteLine(Format(Preorder(root, new List<int>()))); // [1, 2, 4, 5, 3, 6]
        Console.WriteLine(Format(PreorderIterative(root))); // [1, 2, 4, 5, 3, 6]
        Console.WriteLine(Format(Inorder(root, new List<int>()))); // [4, 2, 5, 1, 3, 6]
        Console.WriteLine(Format(InorderIterative(root))); // [4, 2, 5, 1, 3, 6]
        Console.WriteLine(Format(Postorder(root, new List<int>()))); // [4, 5, 2, 6, 3, 1]
        Console.WriteLine(Format(PostorderIterative(root))); // [4, 5, 2, 6, 3, 1]
        Console.WriteLine(Format(LevelOrder(root))); // [[1], [2, 3], [4, 5, 6]]
        Console.WriteLine(Format(LevelOrder(BuildTree(new int?[] { })))); // []
    }

    static string Format(List<int> values) => "[" + string.Join(", ", values) + "]";

    static string Format(List<List<int>> levels) => "[" + string.Join(", ", levels.Select(Format)) + "]";
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Solution {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // Builds a tree from level-order values, where null marks a missing child.
    // This is how LeetCode writes trees down.
    static TreeNode buildTree(Integer[] values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        // Hand out the remaining values two at a time, left child then right, to
        // the nodes in the order they were created.
        while (i < values.length) {
            TreeNode node = queue.poll();
            if (values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    // Node, then left subtree, then right subtree.
    static List<Integer> preorder(TreeNode node, List<Integer> result) {
        if (node == null) return result;
        result.add(node.val); // Visit the node before either subtree.
        preorder(node.left, result);
        preorder(node.right, result);
        return result;
    }

    // Preorder with your own stack in place of the call stack.
    static List<Integer> preorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            // Push the right child first, so the left one comes off the stack first.
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }

    // Left subtree, then node, then right subtree.
    static List<Integer> inorder(TreeNode node, List<Integer> result) {
        if (node == null) return result;
        inorder(node.left, result);
        result.add(node.val); // Visit the node between its subtrees.
        inorder(node.right, result);
        return result;
    }

    // Inorder with your own stack, where each node waits while its left subtree
    // is walked.
    static List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            // Go left as far as possible, pushing each node on the way down.
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val); // Its left subtree is done, so visit it.
            node = node.right; // Then walk its right subtree the same way.
        }
        return result;
    }

    // Left subtree, then right subtree, then node.
    static List<Integer> postorder(TreeNode node, List<Integer> result) {
        if (node == null) return result;
        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.val); // Visit the node after both subtrees.
        return result;
    }

    // Postorder with your own stack, where each node waits until both of its
    // subtrees are done, just as its recursive call would.
    static List<Integer> postorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        TreeNode last = null; // The node visited most recently.
        while (node != null || !stack.isEmpty()) {
            // Go left as far as possible, pushing each node on the way down.
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            TreeNode top = stack.peek();
            // A subtree's root is the last node postorder visits in it, so if the
            // right child was just visited, the right subtree is done.
            if (top.right != null && top.right != last) {
                node = top.right; // Walk the right subtree before visiting top.
            } else {
                result.add(top.val); // Both subtrees are done, so visit it.
                last = stack.pop();
            }
        }
        return result;
    }

    // Values level by level: top to bottom, and left to right within a level.
    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            // The nodes waiting in the queue right now make up exactly one level.
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int k = 0; k < size; k++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(level);
        }
        return levels;
    }

    public static void main(String[] args) {
        TreeNode root = buildTree(new Integer[] {1, 2, 3, 4, 5, null, 6});
        System.out.println(preorder(root, new ArrayList<>())); // [1, 2, 4, 5, 3, 6]
        System.out.println(preorderIterative(root)); // [1, 2, 4, 5, 3, 6]
        System.out.println(inorder(root, new ArrayList<>())); // [4, 2, 5, 1, 3, 6]
        System.out.println(inorderIterative(root)); // [4, 2, 5, 1, 3, 6]
        System.out.println(postorder(root, new ArrayList<>())); // [4, 5, 2, 6, 3, 1]
        System.out.println(postorderIterative(root)); // [4, 5, 2, 6, 3, 1]
        System.out.println(levelOrder(root)); // [[1], [2, 3], [4, 5, 6]]
        System.out.println(levelOrder(buildTree(new Integer[] {}))); // []
    }
}