Tree traversal

2 snippets across 2 stacks — Interview Prep, SQL

DSAInterview Prep

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.

SQLSQL

Recursive CTE

SQL · Advanced

syntax

WITH RECURSIVE cte AS (
  -- base case
  SELECT ... WHERE condition
  UNION ALL
  -- recursive step
  SELECT ... FROM cte JOIN ...
)
SELECT * FROM cte;

example

WITH RECURSIVE org_chart AS (
  -- Base: top-level managers (no manager)
  SELECT id, first_name, manager_id, 1 AS depth
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  -- Recursive: employees who report to someone already in the result
  SELECT e.id, e.first_name, e.manager_id, oc.depth + 1
  FROM employees e
  JOIN org_chart oc ON e.manager_id = oc.id
)
SELECT * FROM org_chart ORDER BY depth, first_name;

output

-- id | first_name | manager_id | depth
-- 1  | Alice      | NULL       | 1
-- 2  | Bob        | 1          | 2
-- 5  | Carol      | 1          | 2
-- 3  | Dave       | 2          | 3

Note Always include a depth counter and a LIMIT or WHERE condition in the outer query to prevent infinite loops from circular references. MySQL 8+ and PostgreSQL support WITH RECURSIVE. Add CYCLE detection in PostgreSQL 14+ with CYCLE clause.