DSA

Trees

Interview Prep · 8 entries

DFS — Inorder Traversal (Left, Root, Right)

syntax

Visit left subtree → process node → visit right subtree.
For BST: inorder gives sorted order.

example

// JavaScript
function inorder(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  return result;
}

// Iterative with stack
function inorderIterative(root) {
  const result = [], stack = [];
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

# Python
def inorder(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

output

Tree:  4
      / \
     2   6
    / \
   1   3
Inorder: [1, 2, 3, 4, 6]

Note Time O(n), Space O(h) where h = tree height. For balanced tree h = log n, for skewed h = n. Know both recursive and iterative versions — interviewers may ask for iterative. Inorder on BST is a common trick to verify sorted property.

inorder traversalDFS inorderBST sorted ordertree traversal

DFS — Preorder & Postorder

syntax

Preorder: Root → Left → Right (useful for copying/serializing trees)
Postorder: Left → Right → Root (useful for deletion, calculating heights)

example

// JavaScript
function preorder(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    result.push(node.val);  // process before children
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return result;
}

function postorder(root) {
  const result = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    dfs(node.right);
    result.push(node.val);  // process after children
  }
  dfs(root);
  return result;
}

# Python
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

output

Tree:  1
      / \
     2   3
Preorder: [1, 2, 3]
Postorder: [2, 3, 1]

Note Both O(n) time, O(h) space. Preorder is the order you would write nodes in serialization. Postorder is natural for bottom-up computations (e.g., calculating subtree sizes or heights). Interviewers may ask: given preorder + inorder, reconstruct the tree.

preorder traversalpostorder traversalDFS treetree reconstruction

BFS — Level Order Traversal

syntax

Use queue. Process nodes level by level.
Capture queue size at start of each level to delineate levels.

example

// JavaScript
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

# Python
from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

output

Tree:   3
       / \
      9  20
     /  / \
    8  15  7
→ [[3], [9, 20], [8, 15, 7]]

Note Time O(n), Space O(w) where w = max width of tree. Variants: zigzag level order (alternate direction), right side view (last node per level), average of levels. BFS is the natural tool whenever you need level-by-level information.

level orderBFS treebreadth first treetree by level

Maximum Depth of Binary Tree

syntax

Recursive: depth = 1 + max(depth(left), depth(right))
Base case: null node has depth 0.

example

// JavaScript
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

# Python
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

output

Tree:  3
      / \
     9  20
       / \
      15  7
→ depth = 3

Note Time O(n), Space O(h). One of the simplest tree recursion problems — great for warming up. Iterative BFS approach: count number of levels. Follow-up: minimum depth (BFS is more efficient — stops at first leaf).

max depthtree heightbinary tree depthrecursive depth

Validate Binary Search Tree

syntax

Pass down valid range (min, max) at each node.
Left child must be in (min, node.val).
Right child must be in (node.val, max).

example

// JavaScript
function isValidBST(root) {
  function validate(node, min, max) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
  }
  return validate(root, -Infinity, Infinity);
}

# Python
def is_valid_bst(root):
    def validate(node, lo, hi):
        if not node:
            return True
        if node.val <= lo or node.val >= hi:
            return False
        return validate(node.left, lo, node.val) and \
               validate(node.right, node.val, hi)
    return validate(root, float('-inf'), float('inf'))

output

Valid BST:  5       Invalid:  5
           / \                / \
          3   7              3   7
         / \                / \
        1   4              1   6 ← 6 > 5 but in left subtree

Note Time O(n), Space O(h). Common mistake: only checking node against its parent. The range-based approach catches nodes that violate a grandparent constraint. Alternative: inorder traversal and verify the sequence is strictly increasing.

validate BSTbinary search treeBST validationvalid BST

Lowest Common Ancestor (LCA)

syntax

If current node is p or q, return it.
Recurse left and right.
If both sides return non-null, current node is the LCA.
Otherwise return whichever side is non-null.

example

// JavaScript
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

# Python
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right

output

Tree:     3
         / \
        5   1
       / \
      6   2
LCA(5, 1) = 3
LCA(5, 6) = 5

Note Time O(n), Space O(h). For BST: exploit sorted property — if both values < node, go left; if both > node, go right; otherwise current node is LCA. This is an O(h) optimization for BSTs. Always clarify: can a node be its own ancestor?

lowest common ancestorLCAtree ancestorcommon parent

Path Sum

syntax

Subtract current node value from target as you recurse.
At a leaf, check if remaining target equals the leaf value.

example

// JavaScript — Has path with target sum (root to leaf)
function hasPathSum(root, target) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === target;
  return hasPathSum(root.left, target - root.val)
      || hasPathSum(root.right, target - root.val);
}

# Python
def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    return has_path_sum(root.left, target - root.val) or \
           has_path_sum(root.right, target - root.val)

output

Tree:     5
         / \
        4   8
       /   / \
      11  13  4
     / \
    7   2
hasPathSum(root, 22) → True (5→4→11→2)

Note Time O(n), Space O(h). Must reach a leaf — internal nodes with matching sum do not count. Variants: return all paths (collect paths in a list), path sum III (any downward path, use prefix sum + hash map). Clarify: root-to-leaf or any path?

path sumroot to leaftree pathtarget sum tree

Serialize & Deserialize Binary Tree (Concept)

syntax

Serialize: BFS or preorder DFS, use a marker for null nodes.
Deserialize: reconstruct from the serialized format using same traversal order.

example

// JavaScript — Preorder approach
function serialize(root) {
  const parts = [];
  function dfs(node) {
    if (!node) { parts.push('X'); return; }
    parts.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return parts.join(',');
}

function deserialize(data) {
  const vals = data.split(',');
  let idx = 0;
  function dfs() {
    if (vals[idx] === 'X') { idx++; return null; }
    const node = new TreeNode(Number(vals[idx++]));
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

# Python
def serialize(root):
    parts = []
    def dfs(node):
        if not node:
            parts.append('X')
            return
        parts.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ','.join(parts)

def deserialize(data):
    vals = iter(data.split(','))
    def dfs():
        val = next(vals)
        if val == 'X':
            return None
        node = TreeNode(int(val))
        node.left = dfs()
        node.right = dfs()
        return node
    return dfs()

output

serialize:   1        → '1,2,X,X,3,4,X,X,5,X,X'
            / \
           2   3
              / \
             4   5

Note Time O(n), Space O(n). The null marker is essential — without it you cannot reconstruct the tree uniquely. BFS approach works too: serialize level by level. This is a common hard interview question. Practice the deserialization — it is the tricky part.

serialize treedeserialize treeencode treetree to string