Binary Tree

A binary tree is a tree where each node has at most two children, usually named left and right. This simple restriction makes binary trees extremely useful and easy to represent.

Binary trees are the foundation for:

• Binary Search Trees (BSTs).
• Heaps.
• Expression trees.
• Many recursive algorithms (e.g. DFS).

Representation

Common ways to represent a binary tree:

• Linked structure:
  • Each node has fields value, left, and right.
• Array representation (for complete trees like heaps):
  • Node at index i:
    • Left child at 2*i + 1.
    • Right child at 2*i + 2.

Most interview questions assume a linked representation with a TreeNode class.

Traversal Orders

For binary trees, three depth‑first traversals are especially important:

• Preorder: visit node → traverse left → traverse right.
• Inorder: traverse left → visit node → traverse right.
• Postorder: traverse left → traverse right → visit node.

Example recursive templates:

JavaCopy
void preorder(TreeNode node) {
    if (node == null) return;
    visit(node);
    preorder(node.left);
    preorder(node.right);
}

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    visit(node);
    inorder(node.right);
}

void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    visit(node);
}

Inorder traversal has a special role in BSTs: it yields nodes in sorted order.

Iterative Traversals (Non-Recursive)

In practice, you may also be asked to write non-recursive traversals using an explicit stack.

Iterative Inorder Traversal

JavaCopy
List<Integer> inorderIter(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        // go as left as possible
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        res.add(curr.val);   // visit in the middle
        curr = curr.right;   // then go right
    }
    return res;
}

Iterative Preorder Traversal

JavaCopy
List<Integer> preorderIter(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);        // visit when popping
        if (node.right != null) { // push right first so left is processed first
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return res;
}

Iterative Postorder Traversal (Two Stacks)

JavaCopy
List<Integer> postorderIter(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> s1 = new ArrayDeque<>();
    Deque<TreeNode> s2 = new ArrayDeque<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode node = s1.pop();
        s2.push(node);
        if (node.left != null) s1.push(node.left);
        if (node.right != null) s1.push(node.right);
    }
    while (!s2.isEmpty()) {
        res.add(s2.pop().val); // left, right, root order
    }
    return res;
}

These iterative versions are direct translations of the recursive definitions using an explicit stack instead of the call stack.

Visual Example with Traversal Orders

Consider the following binary tree:

• Preorder (root, left, right): 1, 2, 4, 5, 3
• Inorder (left, root, right): 4, 2, 5, 1, 3
• Postorder (left, right, root): 4, 5, 2, 3, 1

Walking through this small tree on paper while tracing each traversal is a great way to build intuition for how the recursive templates behave.

Height and Balance

Key notions:

• Height of a tree: maximum depth of any node.
• Balanced binary tree: roughly, the heights of left and right subtrees don’t differ too much.

Balanced trees (like AVL, Red‑Black) maintain O(log n) height, enabling logarithmic search and update operations. Unbalanced trees can degenerate into linked lists (O(n) height).

Where Binary Trees Appear

Binary trees are used for:

• Representing arithmetic expressions (expression trees).
• Syntax trees in compilers.
• Decision trees in ML / rule systems.
• Internal nodes of many indexes and search structures.

Many interview problems assume a generic binary tree (not necessarily a BST), so focus on:

• Recursion patterns.
• Traversal orders.
• Combining information from children to compute a result at the parent.