1372. Longest ZigZag Path in a Binary Tree

MediumTreeDepth-First SearchDynamic ProgrammingBinary Tree
Leetcode Link

Problem Description

You are tasked with finding the longest ZigZag path in a binary tree. A ZigZag path is defined as follows:

  • You first pick any node as a starting point and choose a direction to move in (either left or right).
  • Based on the chosen direction, you move to the corresponding child node (move to the right child if the direction is right, or to the left child if the direction is left).
  • After moving to a child node, you switch the direction for the next move (from right to left or left to right).
  • You repeat the process of moving to the next child node and switching direction until there are no more nodes to visit.

The ZigZag length is the number of nodes you have visited on the path minus one, since a path with a single node has a length of zero. Your objective is to find the length of the longest ZigZag path in the given binary tree.

Flowchart Walkthrough

Let's analyze the approach to solving LeetCode problem 1372. Longest ZigZag Path in a Binary Tree using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: A binary tree is a specific type of graph.

Is it a tree?

  • Yes: The structure in question, being a binary tree, is indeed a type of tree.

Using the flowchart, we immediately reach the decision to use DFS (Depth-First Search), as DFS is ideal for tree-based problems where we need to explore all possible branches, and this problem requires traversing through different paths to find the longest ZigZag path.

Conclusion: The flowchart indicates using DFS for this tree exploration problem.

Intuition

To solve the problem, we employ depth-first search (DFS) to explore each possible path within the tree. The purpose of using DFS is to traverse the tree in a manner where we check every possible ZigZag path starting from each node, considering both the left and right directions.

Here is the intuition behind the DFS approach:

  • We define a recursive DFS function that takes the current node and two integers, l and r, which represent the lengths of the ZigZag path when the last move was to the left (l) or to the right (r), respectively.
  • At each call to the DFS function, if the current node is None (i.e., we can't move further), we return as we've reached the end of a path.
  • We maintain a variable ans to keep track of the maximum length found so far. For each node, we update ans with the maximal value out of ans, l, and r.
  • When we move to a left child (root.left), we increase the length of the ZigZag path for a move to the right (r + 1), and reset the left move length to zero. This is because moving to the left child is considered a right move for the parent node.
  • Similarly, when moving to the right child (root.right), we increase the length of the ZigZag path for a move to the left (l + 1), and reset the right move length to zero.
  • This recursive process continues until all nodes have been visited, and by then we will have recorded the maximum length of all ZigZag paths in the ans variable.

The solution uses a nonlocal declaration for the ans variable to ensure that its value is updated across different recursive calls. Each recursive call processes the current node and then makes two more recursive calls to the child nodes (if they exist), one for each possible direction (left or right) for the next move, continuing the ZigZag pattern.

Learn more about Tree, Depth-First Search, Dynamic Programming and Binary Tree patterns.

Solution Approach

The solution uses a depth-first search (DFS) to explore each possible ZigZag path. Here's a breakdown of the implementation, referring to the Python code provided:

  • We utilize the TreeNode class to represent the structure of the binary tree, where each node has a value (val), a pointer to the left child (left), and a pointer to the right child (right).

  • The Solution class has the method longestZigZag, which initiates the recursive DFS process to find the longest ZigZag path. The method takes a TreeNode as an input, which is the root of the binary tree.

  • Inside longestZigZag, we define a nested function dfs which recursively processes each node of the tree. The dfs function has parameters:

    • root: the current node being processed.
    • l: an integer representing the ZigZag path length when the last move was to the left.
    • r: an integer representing the ZigZag path length when the last move was to the right.

  • The dfs function begins by checking if the current node is None. If it is, that branch of recursion stops because we can't move further down the tree from this node.

  • To keep track of the maximum ZigZag path length found at any point, we use a variable ans which is declared as nonlocal. This ensures that ans can be updated across the different recursive calls and still maintains its most recent value.

  • At each node, we update ans to be the maximum value between the current ans and the values of l and r. This ensures that as we move through the tree, any longer path lengths are captured and kept.

  • When the DFS explores the left subtree by calling dfs(root.left, r + 1, 0), it increments the ZigZag path length for a direction switch to the right (r + 1) and resets the left path length to zero (0). This is because a move to the left child is seen as a previous right move from the parent node's perspective.

  • Conversely, when exploring the right subtree with dfs(root.right, 0, l + 1), it increments the ZigZag path length for a direction switch to the left (l + 1) and resets the right path length to zero (0). A move to the right child is considered as a previous left move.

  • The initial call to the dfs function is made with dfs(root, 0, 0) starting at the root with lengths of 0 for both left and right paths as no moves have been made yet.

  • Once the DFS traversal is complete and all ZigZag paths have been computed, the longest path length is stored in ans, which is returned as the final result.

In summary, the solution effectively utilizes recursive DFS to explore each path, alternating moves and updating the path length while maintaining a global maximum. This is an example of a modified DFS where additional parameters (l and r) are used not only to keep track of the path length but also to encode the state of the ZigZag movement (direction change after each step). The complexity of the algorithm is O(n) where n is the number of nodes in the binary tree since every node is visited exactly once by the DFS traversal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let us consider a small binary tree example:

    1
   / \
  3   2
 /   / \
4   5   6

We would like to find the longest ZigZag path in this binary tree.

Step 1: We start with the root of the tree which is the node with the value 1. A recursive call dfs(root, 0, 0) is made with both l and r initialized to zero since no moves have been made yet.

Step 2: At the root node 1, since it is not None, we have two options to continue the ZigZag path: move to the left child or right child. We make two recursive calls to explore both options:

  • dfs(root.left, r + 1, 0) which is dfs(node 3, 1, 0)
  • dfs(root.right, 0, l + 1) which is dfs(node 2, 0, 1)

In each of these calls, we are ZigZagging from the root now, so the appropriate path lengths l and r are updated.

Step 3: Now in the subtree rooted at 3, we have l = 1, r = 0. Since node 3 has a left child 4 and no right child, we make another recursive call dfs(node 3.left, r + 1, 0) which becomes dfs(node 4, 1, 0). At this point, since node 4 is a leaf node without children, the path ends here, and ans is potentially updated to the maximum of ans, l, or r which in this case would be 1.

Similarly, in the subtree rooted at 2, we have l = 0, r = 1. Node 2 has both a left and a right child, so two recursive calls are made:

  • dfs(node 2.left, r + 1, 0) which is dfs(node 5, 2, 0)
  • dfs(node 2.right, 0, l + 1) which is dfs(node 6, 0, 1)

At each leaf node (5 and 6), the same check for None occurs, and the ans is updated with the path lengths of 2 and 1, respectively.

Step 4: Once all leaves have been reached, and None returned for each childless call, the recursion unwinds. The ans variable that was kept up to date in each step now contains the value 2, which is the longest ZigZag path length in the binary tree (from 1 to 2 to 5).

The longest ZigZag path in this binary tree is therefore of length 2, which corresponds to two moves: one move from root (1) to the right child (2), and another move from the right child (2) to its left child (5). This illustrates how the DFS algorithm zigzags through the tree to find the longest possible path.

Solution Implementation

1class Solution:
2    def longestZigZag(self, root: TreeNode) -> int:
3        # Helper function to perform DFS (Depth-First Search) on the tree
4        def dfs(node, left_length, right_length):
5            # If the node is None, we've reached the end of a path
6            if node is None:
7                return
8            # Update the global answer by taking the maximum value found so far
9            nonlocal max_length
10            max_length = max(max_length, left_length, right_length)
11            # Recursively explore the left child, incrementing the "left_length" as we are
12            # making a zig (left direction) from the right side of the current node
13            dfs(node.left, right_length + 1, 0)
14            # Recursively explore the right child, incrementing the "right_length" as we are
15            # making a zag (right direction) from the left side of the current node
16            dfs(node.right, 0, left_length + 1)
17      
18        # Initialize the maximum length to 0 before starting DFS
19        max_length = 0
20        # Start DFS with the root of the tree, initial lengths are 0 as starting point
21        dfs(root, 0, 0)
22        # Once DFS is complete, return the maximum zigzag length found
23        return max_length
24
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8    TreeNode() {}
9    TreeNode(int val) { this.val = val; }
10    TreeNode(int val, TreeNode left, TreeNode right) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17/**
18 * Solution class contains methods to calculate the longest zigzag path in a binary tree.
19 */
20class Solution {
21    // Variable to store the length of the longest zigzag path found so far.
22    private int longestZigZagLength;
23
24    /**
25     * Method to find the length of the longest zigzag path starting from the root node.
26     *
27     * @param root The root node of the binary tree.
28     * @return The length of the longest zigzag path in the tree.
29     */
30    public int longestZigZag(TreeNode root) {
31        // Initialize with the assumption that there's no zigzag path.
32        longestZigZagLength = 0;
33      
34        // Start Depth First Search traversal from the root.
35        dfs(root, 0, 0);
36      
37        // Return the length of the longest zigzag path found.
38        return longestZigZagLength;
39    }
40
41    /**
42     * A recursive DFS method that traverses the tree to find the longest zigzag path.
43     *
44     * @param node        The current node being visited.
45     * @param leftLength  The current length of the zigzag path when coming from a left child.
46     * @param rightLength The current length of the zigzag path when coming from a right child.
47     */
48    private void dfs(TreeNode node, int leftLength, int rightLength) {
49        // If the node is null, we have reached beyond leaf, so return.
50        if (node == null) {
51            return;
52        }
53      
54        // Update the longestZigZagLength with the maximum path length seen so far at this node.
55        longestZigZagLength = Math.max(longestZigZagLength, Math.max(leftLength, rightLength));
56
57        // Traverse left - the zigzag is coming from the right so add 1 to rightLength.
58        dfs(node.left, rightLength + 1, 0);
59
60        // Traverse right - the zigzag is coming from the left so add 1 to leftLength.
61        dfs(node.right, 0, leftLength + 1);
62    }
63}
64
1#include <algorithm> // For using max()
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;          // Value of the node
6    TreeNode *left;   // Pointer to the left child
7    TreeNode *right;  // Pointer to the right child
8
9    // Constructors
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    int longestPath = 0; // Variable to store the longest ZigZag path length found
18
19    // Function to calculate the length of the longest ZigZag path in a binary tree.
20    int longestZigZag(TreeNode* root) {
21        traverse(root, 0, 0); // Start the traversal from the root node
22        return longestPath;   // Return the longest ZigZag path length found
23    }
24
25    // Helper function to perform DFS and find the length of the longest ZigZag path
26    void traverse(TreeNode* node, int leftSteps, int rightSteps) {
27        if (!node) return; // If we reach a null node, stop the traversal
28      
29        // Update the maximum length of ZigZag path seen so far
30        longestPath = std::max(longestPath, std::max(leftSteps, rightSteps));
31
32        // If we take a left child, we can move right the next step; thus, increment rightSteps.
33        // If we take a right child, we can move left the next step; thus, increment leftSteps.
34        // Pass 0 for the opposite direction because ZigZag path resets on turning twice in the same direction.
35        if (node->left) traverse(node->left, rightSteps + 1, 0);       // Traverse the left child
36        if (node->right) traverse(node->right, 0, leftSteps + 1);      // Traverse the right child
37    }
38};
39
1// Interface for a binary tree node
2interface TreeNode {
3  val: number;        // Value of the node
4  left: TreeNode | null;   // Reference to the left child
5  right: TreeNode | null;  // Reference to the right child
6}
7
8// Variable to store the longest ZigZag path length found
9let longestPath: number = 0;
10
11// Function to calculate the length of the longest ZigZag path in a binary tree
12function longestZigZag(root: TreeNode | null): number {
13  traverse(root, 0, 0); // Start the traversal from the root node
14  return longestPath;   // Return the longest ZigZag path length found
15}
16
17// Helper function to perform DFS and find the length of the longest ZigZag path
18function traverse(node: TreeNode | null, leftSteps: number, rightSteps: number) {
19  if (!node) return; // If we reach a null node, stop the traversal
20
21  // Update the maximum length of the ZigZag path seen so far
22  longestPath = Math.max(longestPath, leftSteps, rightSteps);
23
24  // If we take a left child, we can move right on the next step; thus, increment rightSteps.
25  // If we take a right child, we can move left on the next step; thus, increment leftSteps.
26  // Pass 0 for the opposite direction because the ZigZag path resets on turning twice in the same direction.
27  if (node.left) traverse(node.left, rightSteps + 1, 0); // Traverse the left child
28  if (node.right) traverse(node.right, 0, leftSteps + 1); // Traverse the right child
29}
30

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n) where n is the number of nodes in the binary tree. The reason for this is that the function dfs visits every node in the tree exactly once. During each call, it performs a constant amount of work, regardless of the size of the subtree it is working with.

Space Complexity

The space complexity of the code is O(h), where h is the height of the binary tree. This space is used by the call stack due to recursion. In the worst case, when the binary tree becomes a skewed tree (like a linked list), the height h can be equal to n, which means the space complexity in the worst case would be O(n). However, for a balanced tree, the height h will be log(n), resulting in a space complexity of O(log(n)).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which technique can we use to find the middle of a linked list?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Want a Structured Path to Master System Design Too? Don’t Miss This!