Gyaan

Binary Trees

beginner binary-tree traversal DFS BFS data-structure

A tree is a collection of nodes connected by edges, with no cycles. It’s like a family tree — one node at the top (the root), and everything branches downward. A binary tree is a tree where each node has at most two children — a left child and a right child.

Why do we care? Trees show up everywhere. File systems, HTML DOM, org charts, database indexes — they’re all trees. And in interviews, tree problems are probably the most commonly asked category.

Terminology

Let’s get the vocabulary down first:

Binary Tree Anatomy
root, depth 0 →
8
← height 3
╱ ╲
depth 1 →
3
10
╱ ╲ ╱ ╲
depth 2 →
1
6
9
14
Leaves: 1, 6, 9, 14 (no children)  |  Internal nodes: 8, 3, 10 (have children)
  • Root — the topmost node (8 in our tree). It has no parent.
  • Leaf — a node with no children (1, 6, 9, 14).
  • Internal node — a node that has at least one child.
  • Depth — how far a node is from the root. Root is depth 0.
  • Height — the longest path from a node down to a leaf. The tree’s height is the height of the root.
  • Parent / Child — node 3 is a child of 8. Node 8 is the parent of 3.
  • Subtree — any node and all its descendants form a subtree.

Node Definition

Every tree node holds a value and pointers to its left and right children.

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;   // left child
    this.right = null;  // right child
  }
}
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None   # left child
        self.right = None  # right child
class TreeNode {
    int val;
    TreeNode left;    // left child
    TreeNode right;   // right child
    TreeNode(int val) { this.val = val; }
}

Tree Traversals

Traversal means visiting every node exactly once. There are four main ways to do it, and they come up in almost every tree interview problem.

Inorder (Left, Node, Right)

Go left as far as we can, visit the node, then go right. For a BST, this gives us nodes in sorted order.

function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);    // go left
  result.push(node.val);         // visit node
  inorder(node.right, result);   // go right
  return result;
}
// Tree above: [1, 3, 6, 8, 9, 10, 14]
def inorder(node, result=None):
    if result is None: result = []
    if not node: return result
    inorder(node.left, result)    # go left
    result.append(node.val)       # visit node
    inorder(node.right, result)   # go right
    return result
# Tree above: [1, 3, 6, 8, 9, 10, 14]
void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);    // go left
    result.add(node.val);          // visit node
    inorder(node.right, result);   // go right
}
// Tree above: [1, 3, 6, 8, 9, 10, 14]

Preorder (Node, Left, Right)

Visit the node first, then go left, then right. This is useful for copying/serializing a tree.

function preorder(node, result = []) {
  if (!node) return result;
  result.push(node.val);          // visit node first
  preorder(node.left, result);    // then left
  preorder(node.right, result);   // then right
  return result;
}
// Tree above: [8, 3, 1, 6, 10, 9, 14]
def preorder(node, result=None):
    if result is None: result = []
    if not node: return result
    result.append(node.val)        # visit node first
    preorder(node.left, result)    # then left
    preorder(node.right, result)   # then right
    return result
# Tree above: [8, 3, 1, 6, 10, 9, 14]
void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);          // visit node first
    preorder(node.left, result);   // then left
    preorder(node.right, result);  // then right
}
// Tree above: [8, 3, 1, 6, 10, 9, 14]

Postorder (Left, Right, Node)

Go left, go right, then visit the node last. This is useful for deleting a tree (delete children before parent).

function postorder(node, result = []) {
  if (!node) return result;
  postorder(node.left, result);   // go left
  postorder(node.right, result);  // go right
  result.push(node.val);          // visit node last
  return result;
}
// Tree above: [1, 6, 3, 9, 14, 10, 8]
def postorder(node, result=None):
    if result is None: result = []
    if not node: return result
    postorder(node.left, result)   # go left
    postorder(node.right, result)  # go right
    result.append(node.val)        # visit node last
    return result
# Tree above: [1, 6, 3, 9, 14, 10, 8]
void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorder(node.left, result);   // go left
    postorder(node.right, result);  // go right
    result.add(node.val);           // visit node last
}
// Tree above: [1, 6, 3, 9, 14, 10, 8]

Level-Order (BFS)

Visit nodes level by level, left to right. This uses a queue instead of recursion.

function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const node = queue.shift();    // dequeue front
    result.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}
// Tree above: [8, 3, 10, 1, 6, 9, 14]
from collections import deque

def level_order(root):
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()     # dequeue front
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result
# Tree above: [8, 3, 10, 1, 6, 9, 14]
List<Integer> levelOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // dequeue front
        result.add(node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return result;
}
// Tree above: [8, 3, 10, 1, 6, 9, 14]

Traversal Summary

Traversal Order Cheatsheet
Inorder Left → Node → Right → sorted order (BST)
Preorder Node → Left → Right → copy/serialize tree
Postorder Left → Right → Node → delete tree
Level-order Level by level (BFS) → shortest path, level grouping

Max Depth of a Binary Tree

This is one of the most classic tree problems. The depth of a tree is 1 + max(depth of left subtree, depth of right subtree).

function maxDepth(node) {
  if (!node) return 0;             // empty tree has depth 0
  const left = maxDepth(node.left);
  const right = maxDepth(node.right);
  return 1 + Math.max(left, right); // current node + deeper subtree
}
def max_depth(node):
    if not node: return 0            # empty tree has depth 0
    left = max_depth(node.left)
    right = max_depth(node.right)
    return 1 + max(left, right)      # current node + deeper subtree
int maxDepth(TreeNode node) {
    if (node == null) return 0;       // empty tree has depth 0
    int left = maxDepth(node.left);
    int right = maxDepth(node.right);
    return 1 + Math.max(left, right); // current node + deeper subtree
}

Time: O(n) — we visit every node. Space: O(h) — where h is the height (call stack depth).

Check if Tree is Symmetric

A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

function isSymmetric(root) {
  if (!root) return true;
  return isMirror(root.left, root.right);
}
function isMirror(a, b) {
  if (!a && !b) return true;         // both null = mirror
  if (!a || !b) return false;        // one null = not mirror
  return a.val === b.val             // same value
    && isMirror(a.left, b.right)     // outer pair
    && isMirror(a.right, b.left);    // inner pair
}
def is_symmetric(root):
    if not root: return True
    return is_mirror(root.left, root.right)

def is_mirror(a, b):
    if not a and not b: return True   # both None = mirror
    if not a or not b: return False   # one None = not mirror
    return (a.val == b.val            # same value
        and is_mirror(a.left, b.right)  # outer pair
        and is_mirror(a.right, b.left)) # inner pair
boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}
boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val              // same value
        && isMirror(a.left, b.right)   // outer pair
        && isMirror(a.right, b.left);  // inner pair
}

Time: O(n) — visit every node once. Space: O(h) — recursion stack.

Key Takeaways

  • A binary tree is just nodes with at most two children. No special ordering required.
  • The four traversals (inorder, preorder, postorder, level-order) are the bread and butter of tree problems. Learn them cold.
  • DFS traversals (inorder, preorder, postorder) use recursion (or a stack). BFS (level-order) uses a queue.
  • Most tree problems follow the same recursive pattern: handle null, do something with current node, recurse on left and right.

In simple language, if we can write a recursive function that handles the base case (null node) and combines results from left and right subtrees, we can solve most tree problems.

References