Where have I been? And Understanding Stack Usage in DFS Traversals for Binary Trees

Hey guys,

I’ve been out of pocket for a few months here.

I know.

Here’s why.

I honestly don’t know if anyone finds this stuff useful so I’ve stopped.

But - a good friend of mine reminded me that it does help people so I promise, going forward i’ll write weekly.

But - I also want to write about career growth and how to get to the next level in your career in tech, not just DSA and System Design.

Hope you don’t mind.

Understanding Stack Usage in DFS Traversals for Binary Trees

When solving binary tree problems, especially those involving Depth-First Search (DFS), using a stack is common. The stack helps you keep track of nodes and relevant state information as you traverse the tree. Let’s break down how to use and build stacks in simple terms, with examples from Leetcode. Problems like the Lowest Common Ancestor and Longest ZigZag Path.

Basics of Stack in DFS Traversal

1. A stack is a data structure that follows the Last In, First Out (LIFO) principle. In the context of tree traversal, it helps you manage nodes and their associated states during the search.
2. When starting a DFS traversal, you initialize the stack with the root node and any other initial state needed. For instance:
3. Here, each element of the stack is a tuple (a data structure that represents an ordered, immutable collection of elements) containing a node and an associated state (in this case, an array).

Example 1: Path Sum III

Problem: Find paths in a binary tree where the sum of the node values equals a target value.

Stack Initialization:

const stack: [TreeNode, number[]][] = [[root, []]];        

TreeNode: The current node being processed.

number[]: A list that tracks the path values from the root to the current node.

How it Works:

1. Start with the root node and an empty path list(array).
2. Traverse Tree:

Conditionally Push Values:

if (node.left) { 
stack.push([node.left, [...path, node.left.val]]); 

} if (node.right) { 

stack.push([node.right, [...path, node.right.val]]); 

}        

Example 2: Longest ZigZag Path

Problem: Find the longest ZigZag path in a binary tree, where you can alternate between left and right directions.

Stack Initialization:

const stack: [TreeNode, string, number][] = [[root, '', 0]];        

TreeNode: The current node.

string: A string that tracks the direction (e.g., 'Left' or 'Right') for ZigZag.

number: The length of the current ZigZag path.

How it Works:

1. Start with the root node, an empty direction string, and a length of 0.
2. Traverse Tree:

Conditionally Push Values:

if (direction === '') { stack.push([node.left, 'L', length + 1]); stack.push([node.right, 'R', length + 1]); 

} else if (direction === 'L') { 

stack.push([node.right, 'R', length + 1]); 

} 
else if (direction === 'R') { 

stack.push([node.left, 'L', length + 1]); 

}        

When building stacks for DFS problems:

1. Determine what state information needs to be tracked (e.g., path values, direction).
2. Start with the root node and/or relevant initial state.
3. Push new nodes and updated states based on traversal conditions and problem requirements.

Thanks!

P.S. If you like this kind of stuff, subscribe to my newsletter at learndsa.io!

And please share and like this!