Binary trees are hierarchical data structures with nodes containing up to two children. Common types include full binary trees where every node has either zero or two children, and complete binary trees where all levels are fully filled except possibly the last level.

Storage methods include linked storage using node references and sequential storage using arrays with index-based child access. Traversal methods fall into two categories:

• Depth-First Search (DFS): Explorse paths to leaf nodes before backtracking
• Breadth-First Search (BFS): Processes nodes level by level

DFS includes three primary traversal orders:

• Pre-order: Root → Left subtree → Right subtree
• In-order: Left subtree → Root → Right subtree
• Post-order: Left subtree → Right subtree → Root

BFS is implemented through level-order traversal. Below is a standard tree node implementation:

public class BinaryNode {
  int value;
  BinaryNode leftChild;
  BinaryNode rightChild;
  
  BinaryNode() {}
  BinaryNode(int val) { value = val; }
  BinaryNode(int val, BinaryNode left, BinaryNode right) {
    value = val;
    leftChild = left;
    rightChild = right;
  }
}

Pre-order Traversal

Recursive implementation:

public List<Integer> preorder(BinaryNode root) {
  List<Integer> output = new ArrayList<>();
  traversePre(root, output);
  return output;
}

private void traversePre(BinaryNode node, List<Integer> output) {
  if (node == null) return;
  output.add(node.value);
  traversePre(node.leftChild, output);
  traversePre(node.rightChild, output);
}

Iterative implementation using stack:

public List<Integer> preorderIterative(BinaryNode root) {
  List<Integer> output = new ArrayList<>();
  if (root == null) return output;
  
  Stack<BinaryNode> nodeStack = new Stack<>();
  nodeStack.push(root);
  
  while (!nodeStack.isEmpty()) {
    BinaryNode current = nodeStack.pop();
    output.add(current.value);
    if (current.rightChild != null) nodeStack.push(current.rightChild);
    if (current.leftChild != null) nodeStack.push(current.leftChild);
  }
  return output;
}

In-order Traversal

Recursive implementation:

public List<Integer> inorder(BinaryNode root) {
  List<Integer> output = new ArrayList<>();
  traverseIn(root, output);
  return output;
}

private void traverseIn(BinaryNode node, List<Integer> output) {
  if (node == null) return;
  traverseIn(node.leftChild, output);
  output.add(node.value);
  traverseIn(node.rightChild, output);
}

Iterative implementation:

public List<Integer> inorderIterative(BinaryNode root) {
  List<Integer> output = new ArrayList<>();
  Stack<BinaryNode> nodeStack = new Stack<>();
  BinaryNode current = root;
  
  while (current != null || !nodeStack.isEmpty()) {
    if (current != null) {
      nodeStack.push(current);
      current = current.leftChild;
    } else {
      current = nodeStack.pop();
      output.add(current.value);
      current = current.rightChild;
    }
  }
  return output;
}

Post-order Traversal

Recursive implementation:

public List<Integer> postorder(BinaryNode root) {
  List<Integer> output = new ArrayList<>();
  traversePost(root, output);
  return output;
}

private void traversePost(BinaryNode node, List<Integer> output) {
  if (node == null) return;
  traversePost(node.leftChild, output);
  traversePost(node.rightChild, output);
  output.add(node.value);
}

Iterative implementation:

public List<Integer> postorderIterative(BinaryNode root) {
  List<Integer> output = new ArrayList<>();
  if (root == null) return output;
  
  Stack<BinaryNode> nodeStack = new Stack<>();
  nodeStack.push(root);
  
  while (!nodeStack.isEmpty()) {
    BinaryNode current = nodeStack.pop();
    output.add(0, current.value);
    if (current.leftChild != null) nodeStack.push(current.leftChild);
    if (current.rightChild != null) nodeStack.push(current.rightChild);
  }
  return output;
}

Level-order Traversal

public List<List<Integer>> levelOrder(BinaryNode root) {
  List<List<Integer>> result = new ArrayList<>();
  traverseLevels(root, result, 0);
  return result;
}

private void traverseLevels(BinaryNode node, List<List<Integer>> result, int depth) {
  if (node == null) return;
  depth++;
  
  if (result.size() < depth) {
    result.add(new ArrayList<>());
  }
  result.get(depth - 1).add(node.value);
  
  traverseLevels(node.leftChild, result, depth);
  traverseLevels(node.rightChild, result, depth);
}