2 min read algorithm

Depth-First Search for Advanced Binary Tree Problems in JavaScript

Explore how Depth-First Search (DFS) can solve complex problems in binary trees with a focus on finding unique paths in JavaScript.

Depth-First Search for Advanced Binary Tree Problems in JavaScript

Depth-First Search (DFS) is a powerful technique used in traversing or searching tree or graph data structures. It’s particularly useful in binary trees for solving complex problems that require exploring all possible paths in a tree.

Why Depth-First Search in Binary Trees?

  • Comprehensive Node Exploration: DFS ensures that all nodes in the tree are thoroughly explored, making it perfect for path-finding problems.
  • Adaptability: Can be tailored to solve a variety of complex problems in binary trees, including finding unique paths or calculating maximum lengths.
  • Efficiency: DFS is naturally suited for recursion, making it a go-to method for efficiently exploring tree structures.

Understanding the Basics:

DFS involves traversing as deep as possible into a tree before backtracking, which can be elegantly implemented using recursion.

Example: Finding the Longest ZigZag Path

Problem Statement:

Implement a function to find the longest zigzag path in a binary tree, where a zigzag path is defined as a sequence of nodes with alternating left and right children.

Solution Using DFS:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;

function longestZigZag(root) {
  let maxPath = 0;

  function dfs(node, isLeft, length) {
    if (node === null) return;
    maxPath = Math.max(maxPath, length);
    if (isLeft) {
      dfs(node.left, false, length + 1);
      dfs(node.right, true, 1);
    } else {
      dfs(node.right, true, length + 1);
      dfs(node.left, false, 1);

  dfs(root, false, 0);
  dfs(root, true, 0);
  return maxPath;

How the Code Works:

  • TreeNode Class: A simple class for creating nodes of a binary tree.
  • DFS Function: The dfs function recursively traverses the tree, tracking the length of the current zigzag path.
  • Tracking ZigZag Path: It alternates between left and right children, increasing the path length when the direction changes.
  • Max Path Calculation: The maximum zigzag path length is updated whenever a longer path is found.

Read Next

This post explores the implementation of the Binary Search algorithm in JavaScript, demonstrated through a function for calculating successful pairs.
Dive into the effective use of Heaps and Priority Queues in JavaScript to optimize complex algorithmic challenges, illustrated with a practical example.