1372. Longest ZigZag Path in a Binary Tree
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
andr
, 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 updateans
with the maximal value out ofans
,l
, andr
. - 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 methodlongestZigZag
, which initiates the recursive DFS process to find the longest ZigZag path. The method takes aTreeNode
as an input, which is theroot
of the binary tree. -
Inside
longestZigZag
, we define a nested functiondfs
which recursively processes each node of the tree. Thedfs
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 isNone
. 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 asnonlocal
. This ensures thatans
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 currentans
and the values ofl
andr
. 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 withdfs(root, 0, 0)
starting at theroot
with lengths of0
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 EvaluatorExample 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 isdfs(node 3, 1, 0)
dfs(root.right, 0, l + 1)
which isdfs(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 isdfs(node 5, 2, 0)
dfs(node 2.right, 0, l + 1)
which isdfs(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.
How does quick sort divide the problem into subproblems?
Recommended Readings
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
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
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!