Skip to main content
Mapagam

Implementing Tree Depth-First Search

1. Understanding DFS Traversals

Traversal Type Description Use Case Example
Pre-order Visit node, then left subtree, then right subtree Tree serialization, copying trees 
function dfsPreorder(node) {
  if (node === null) return;
  console.log(node.value);
  dfsPreorder(node.left);
  dfsPreorder(node.right);
}
In-order Visit left subtree, then node, then right subtree Binary search tree sorting 
function dfsInorder(node) {
  if (node === null) return;
  dfsInorder(node.left);
  console.log(node.value);
  dfsInorder(node.right);
}
Post-order Visit left subtree, then right subtree, then node Deleting nodes, calculating file sizes 
function dfsPostorder(node) {
  if (node === null) return;
  dfsPostorder(node.left);
  dfsPostorder(node.right);
  console.log(node.value);
}

Example: Tree Node Structure

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
Note: DFS traversals can be implemented recursively or iteratively using a stack.

2. Finding All Root-to-Leaf Paths

Property Description Example
path Current path from root to current node [1, 2, 4]
leaf Indicates if current node is a leaf true

Example: Collecting All Root-to-Leaf Paths

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function findAllPaths(root) {
  const paths = [];
  
  function dfs(node, currentPath) {
    if (!node) return;
    
    currentPath.push(node.val);
    
    if (!node.left && !node.right) {
      paths.push([...currentPath]);
    } else {
      dfs(node.left, currentPath);
      dfs(node.right, currentPath);
    }
    
    currentPath.pop();
  }
  
  dfs(root, []);
  return paths;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(findAllPaths(root));
// Output: [[1, 2, 4], [1, 2, 5], [1, 3]]
Note: The path is maintained using a stack-like approach where we push to the current path when entering a node and pop when backtracking.

3. Checking Path Sum

Property Description Example
pathSum Checks if there's a root-to-leaf path with the given sum. 
function hasPathSum(root, targetSum) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === targetSum;
  return hasPathSum(root.left, targetSum - root.val) || 
         hasPathSum(root.right, targetSum - root.val);
}

Example: Path Sum Check

const root = {
  val: 5,
  left: { val: 4, left: { val: 11, left: { val: 7 }, right: { val: 2 } }, right: null },
  right: { val: 8, left: { val: 13 }, right: { val: 4, right: { val: 1 } } }
};

console.log(hasPathSum(root, 22)); // true (5->4->11->7)

4. Finding All Path Sums

Example: Finding All Path Sums in a Binary Tree

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function findAllPathSums(root, targetSum) {
  const result = [];
  dfs(root, [], targetSum, result);
  return result;
}

function dfs(node, path, remainingSum, result) {
  if (!node) return;

  path.push(node.val);
  remainingSum -= node.val;

  if (remainingSum === 0 && !node.left && !node.right) {
    result.push([...path]);
  } else {
    dfs(node.left, path, remainingSum, result);
    dfs(node.right, path, remainingSum, result);
  }

  path.pop();
}

// Example usage:
const root = new TreeNode(5, 
  new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
  new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1)))
);

console.log(findAllPathSums(root, 22)); 
// Output: [[5,4,11,2], [5,8,4,1]]
Property Description Notes
root Root node of the binary tree Must be a valid TreeNode or null
targetSum Target sum to find paths for Integer value
result Array of all valid paths Each path is an array of node values
Note: This algorithm uses backtracking to explore all paths from root to leaf nodes. It ensures that only complete paths (from root to leaf) are considered for sum calculation.

5. Finding Path with Maximum Sum

Property Description Example
maxSumPath Finds the path with maximum sum from root to any leaf node in a binary tree 
function maxSumPath(root) {
  if (!root) return 0;
  return root.val + Math.max(maxSumPath(root.left), maxSumPath(root.right));
}

Example: Maximum Path Sum in Binary Tree

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

function maxSumPath(node) {
  if (!node) return 0;
  const left = maxSumPath(node.left);
  const right = maxSumPath(node.right);
  return node.val + Math.max(left, right);
}

console.log(maxSumPath(root)); // Output: 9 (path: 1 -> 2 -> 5)
Note: This algorithm uses a recursive DFS approach to compute the maximum sum path from root to any leaf node.

6. Finding Path Sequence

Property Description Example
path Array to store the current path from root to current node []
result Array to store all valid paths from root to leaf nodes []

Example: Finding All Root-to-Leaf Paths

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function findPaths(root) {
  const result = [];
  dfs(root, [], result);
  return result;
}

function dfs(node, path, result) {
  if (!node) return;

  // Add current node to the path
  path.push(node.val);

  // If it's a leaf node, save the path
  if (!node.left && !node.right) {
    result.push([...path]);
  } else {
    // Continue DFS on children
    dfs(node.left, path, result);
    dfs(node.right, path, result);
  }

  // Backtrack: remove current node from path
  path.pop();
}

// Example usage:
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(9);

console.log(findPaths(root));
// Output: [[5, 3, 2], [5, 3, 4], [5, 8, 9]]
Note: The path array is modified during traversal and must be cloned when added to the result to preserve its state.

7. Counting Paths for Sum

Given a binary tree and a target sum, count the number of paths where the sum of node values equals the target sum. A path can start and end at any nodes, but must travel downward (from parent to child).

Property Description Example
pathSum(root, targetSum) Counts all downward paths in the tree with sum equal to targetSum pathSum([5,4,8,11,null,13,4,7,2,null,null,5,1], 22) returns 3

Example: Count Paths with Sum

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function pathSum(root, targetSum) {
  if (!root) return 0;

  const dfs = (node, currentSum) => {
    if (!node) return 0;
    currentSum += node.val;
    let count = 0;
    if (currentSum === targetSum) count++;
    return count + dfs(node.left, currentSum) + dfs(node.right, currentSum);
  };

  return dfs(root, 0) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}

// Example usage:
const root = new TreeNode(5, 
  new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
  new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1)))
);

console.log(pathSum(root, 22)); // Output: 3
Note: The algorithm uses a recursive approach combining root-to-leaf path sums with recursive exploration of subtrees to ensure all possible paths are considered.

8. Finding Tree Diameter

The diameter of a tree is the number of edges in the longest path between any two nodes in the tree.

Property Description Notes
Tree Diameter Maximum distance between any two nodes in the tree Measured in edges, not nodes

Example: Finding Diameter of Binary Tree

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function dfs(node) {
    if (!node) return 0;
    
    const leftHeight = dfs(node.left);
    const rightHeight = dfs(node.right);
    
    const currentDiameter = leftHeight + rightHeight;
    maxDiameter = Math.max(maxDiameter, currentDiameter);
    
    return Math.max(leftHeight, rightHeight) + 1;
  }

  dfs(root);
  return maxDiameter;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(diameterOfBinaryTree(root)); // Output: 3
Note: The diameter is calculated as the sum of the heights of the left and right subtrees at the node that maximizes this value.

9. Finding Maximum Path Sum

Property Description Example
maxPathSum Maximum sum of any path in the tree 15
path Path that achieves maximum sum [1, 2, 5]

Example: Maximum Path Sum in Binary Tree

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root) {
  let maxSum = -Infinity;

  function dfs(node) {
    if (!node) return 0;
    
    const left = Math.max(dfs(node.left), 0);
    const right = Math.max(dfs(node.right), 0);
    
    const currentSum = node.val + left + right;
    maxSum = Math.max(maxSum, currentSum);
    
    return node.val + Math.max(left, right);
  }

  dfs(root);
  return maxSum;
}

// Example usage:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(maxPathSum(root)); // Output: 12 (path: 4 -> 2 -> 1 -> 3)
Note: The maximum path sum can include any combination of nodes in the tree, not necessarily passing through the root.

10. Calculating Sum of Path Numbers

Property Description Example
pathSum Recursive function to calculate sum of all root-to-leaf path numbers 
function pathSum(root) {
  return calculatePathSum(root, 0);
}

function calculatePathSum(node, currentSum) {
  if (!node) return 0;
  
  currentSum = currentSum * 10 + node.val;
  
  if (!node.left && !node.right) {
    return currentSum;
  }
  
  return calculatePathSum(node.left, currentSum) +
         calculatePathSum(node.right, currentSum);
}

Example: Calculating Path Sum

const root = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null
  },
  right: {
    val: 3,
    left: null,
    right: null
  }
};

console.log(pathSum(root)); // Output: 25

11. Finding Kth Smallest Element

Property Description Example
kthSmallest(root, k) Finds the kth smallest element in a BST findKthSmallest(root, 3)

Example: In-order Traversal

function kthSmallest(root, k) {
  const stack = [];
  let count = 0;
  let current = root;

  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();
    count++;

    if (count === k) {
      return current.val;
    }

    current = current.right;
  }

  return null;
}
Note: This approach uses iterative in-order traversal to avoid recursion stack overflow for large trees.

Algorithm Summary

  • Traverse the BST in-order (left → root → right)
  • Keep a counter to track visited nodes
  • Return the value when counter equals k

12. Validating Binary Search Tree

Property Description Notes
isValidBST Checks if a binary tree is a valid BST Valid BST must satisfy the property that all nodes in left subtree are less than root, and all nodes in right subtree are greater

Example: Validating BST

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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);
}

// Example usage:
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);

console.log(isValidBST(root)); // true
Note: The validation uses a range-based approach to ensure each node's value is within the valid bounds determined by its ancestors.

Was this article helpful?

Related Cheat Sheets