[Algorithm] 10.Binary Tree Traversal

10.Binary Tree Traversal (Binary Search Tree (BST))

Search Direction

PreOrder : root -> left -> right
InOrder : left -> root -> right
PostOrder : left -> right -> root

Search Algorithm

DFS (Depth-First Search) : Stack push / pop
BFS (Breadth-First Search) : Queue push / shift

Find child index
leftChild : prarentIndex 2 + 1
rightChild : parentIndex 2 + 2

Find parent index
Math.floor(childIndex / 2)

input

/**
 
 -10
/    \
9      20
     /    \
   15     7

*/
const root = new TreeNode(
  -10,
  new TreeNode(9),
  new TreeNode(20, new TreeNode(15), new TreeNode(7))
);

1. PreOrder → Binary Tree Paths (LeetCode #257)

DFS

// Depth-First Search (DFS).
// DFS (Stack) is usually more memory-efficient for trees that are deep but not very wide.
function binaryTreePathsDFS(root: TreeNode | null): string[] {
  if (!root) return [];

  const result: string[] = [];
  const stack: { node: TreeNode; path: string }[] = [
    { node: root, path: `${root.val}` },
  ];

  while (stack.length > 0) {
    const { node, path } = stack.pop()!;
    if (!node.left && !node.right) {
      result.push(path);
    }

    if (node.left) {
      stack.push({ node: node.left, path: `${path}->${node.left.val}` });
    }
    if (node.right) {
      stack.push({ node: node.right, path: `${path}->${node.right.val}` });
    }
  }

  return result;
}

DFS(Recursive)

// DFS
function binaryTreePathsRecursive(root: TreeNode | null): string[] {
  const path: number[] = [];
  const result: string[] = [];

  function traverse(node: TreeNode | null) {
    if (!node) return;
    path.push(node.val);
    if (!node.left && !node.right) {
      result.push(path.join("->"));
    } else {
      traverse(node.left);
      traverse(node.right);
    }
    path.pop();
  }

  traverse(root);

  return result;
}

BFS

// Breadth-First Search (BFS).
// BFS (Queue) is better for balanced trees since it explores level by level.
function binaryTreePathsBFS(root: TreeNode | null): string[] {
  if (!root) return [];

  const result: string[] = [];
  const queue: { node: TreeNode; path: string }[] = [
    { node: root, path: `${root.val}` },
  ];

  while (queue.length) {
    const { node, path } = queue.shift()!;

    if (!node.left && !node.right) {
      result.push(path);
    }

    if (node.left) {
      queue.push({ node: node.left, path: `${path}->${node.left.val}` });
    }

    if (node.right) {
      queue.push({ node: node.right, path: `${path}->${node.right.val}` });
    }
  }

  return result;
}

2. InOrder → Kth Smallest Element in a BST (LeetCode #230)

The best approach is inorder traversal because:
BST Inorder Traversal (Left → Node → Right) produces sorted values in ascending order.
Stop early when we find the kth element (O(k) complexity instead of O(n) in worst case).
Best Solution: Iterative Inorder Traversal (Using Stack)
Time Complexity: O(k)
Space Complexity: O(h) (h = tree height, worst case O(n) for skewed trees, O(log n) for balanced trees)

iterator

function kthSmallestIterative(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];

  let current: TreeNode | null = root;

  for (let i = 1; i <= k; i++) {
    // Push all left subtree
    while (current) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop()!;
    if (i === k) return current.val;
    current = current.right; // Move to right subtree
  }
  return -1; // This should never be reached if k is valid
}

Recursive

// Binary Search Tree (BST)
// Recursive
function kthSmallest(root: TreeNode | null, k: number): number {
  let ans: number | null = null;

  const dfs = (node: TreeNode | null) => {
    if (!node || ans !== null) return;

    dfs(node.left);

    k--;

    if (k === 0) {
      ans = node.val;
      return;
    }

    dfs(node.right);
  };

  dfs(root);

  return ans!;
}

3. PostOrder → Binary Tree Maximum Path Sum (LeetCode #124)

// PostOrder Traversal : Bottom-Up (left right root )
function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;

  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const leftMax = Math.max(dfs(node.left), 0);
    const rightMax = Math.max(dfs(node.right), 0);

    const localMax = node.val + leftMax + rightMax;

    maxSum = Math.max(maxSum, localMax);

    // Returns the max gain from one side of the subtree
    // since a valid path cannot split into two branches.
    return localMax + Math.max(leftMax, rightMax);
  }

  dfs(root);
  return maxSum;
}