Longest zigzag path in a binary tree

Dynamic Programming Tree Depth-First Search Binary Tree

67.0% acceptance

Feb 25, 2026

3742

You are given the root of a binary tree. A ZigZag path for a binary tree is defined as follow: Choose any node in the binary tree and a direction (right or left). If the current direction is right, move to the right child of the current node; otherwise, move to the left child. Change the direction from right to left or from left to right. Repeat the second and third steps until you can't move in the tree. Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0). Return the longest ZigZag path contained in that tree.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_zig_zag(root: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>) -> i32 {
    // Returns (left_len, right_len, max_in_subtree)
    fn dfs(node: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>) -> (i32, i32, i32) {
      match node {
        None => (-1, -1, 0),
        Some(n) => {
          let n = n.borrow();
          let (_ll, lr, lm) = dfs(n.left.clone());
          let (rl, _rr, rm) = dfs(n.right.clone());
          let left_len = lr + 1;  // went left, then zigzag right
          let right_len = rl + 1; // went right, then zigzag left
          let max_here = left_len.max(right_len).max(lm).max(rm);
          (left_len, right_len, max_here)
        }
      }
    }
    dfs(root).2
  }
}