Posted on by Kalkicode
Code Binary Tree

Longest zig zag path in a binary tree

The problem at hand is to find the length of the longest zigzag path in a given binary tree. In a zigzag path, you move from a parent node to its child node and then to another child node, but you alternate between left and right children.

Problem Statement

Given a binary tree, we need to find the length of the longest zigzag path.

Description and Example

Let's consider a binary tree as shown in the provided code:

Longest length zig zag path

In this example, the longest zigzag path is 1 → 3 → 6 → 4 → 1, which contains 5 nodes. This path alternates between left and right directions.

Idea to Solve

To solve this problem, we can perform a depth-first traversal of the binary tree while keeping track of the zigzag path lengths. We need to maintain two values for each node: the length of the zigzag path that ends with a left child, and the length of the zigzag path that ends with a right child. As we traverse the tree, we update these values based on the direction of the current node's parent.

Algorithm

  1. Create a function zigzagPath that takes a node, a pointer to the result, and a direction (0 for left, 1 for right).

  2. If the node is NULL, return -1.

  3. If the node is a leaf (both left and right children are NULL), return 0.

  4. Recursively traverse the left subtree and right subtree using zigzagPath function. For each subtree, add 1 to the length of the path returned.

  5. Calculate the length of the zigzag path that ends with the current node. For the left direction, it would be the length from the right subtree plus 1, and for the right direction, it would be the length from the left subtree plus 1.

  6. Update the result by taking the maximum of the current result and the calculated zigzag path length.

  7. Depending on the direction, return the length of the zigzag path that ends with the current node.

  8. Create a function longestZigzag that takes the root of the binary tree.

  9. Initialize the result variable to 0.

  10. Call the zigzagPath function twice for both directions (left and right).

  11. If the result is still 0, print "None" to indicate that there is no zigzag path. Otherwise, print the longest zigzag path length.

Pseudocode

function zigzagPath(node, result, direction):
    if node is NULL:
        return -1
    else if node is a leaf:
        return 0
    
    l = zigzagPath(node.left, result, 1) + 1
    r = zigzagPath(node.right, result, 0) + 1
    
    update result with max(result, max(l, r))
    
    if direction is 1:
        return r
    else:
        return l

function longestZigzag(root):
    result = 0
    if root is not NULL:
        zigzagPath(root, result, 0)
        zigzagPath(root, result, 1)
    
    if result is 0:
        print "None"
    else:
        print "Longest zigzag:", result

Code Solution

/*
    C Program 
    Longest zig zag path in a binary tree
*/
#include <stdio.h>
#include <stdlib.h>

// Tree Node
struct TreeNode
{
	int data;
	struct TreeNode *left;
	struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
	struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
	// Create dynamic node
	struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create tree Tree\n");
	}
	//return new tree
	return tree;
}
// returns a new node of tree
struct TreeNode *newNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
// Returns the max of given two numbers
int maxValue(int l, int r)
{
	if (l > r)
	{
		return l;
	}
	else
	{
		return r;
	}
}
// Find zigzag Path
int zigzagPath(struct TreeNode *node, int *result, int direction)
{
	if (node == NULL)
	{
		return -1;
	}
	else if (node->left == NULL && node->right == NULL)
	{
		return 0;
	}
	// Recursively visit left and right subtree
	int l = zigzagPath(node->left, result, 1) + 1;
	int r = zigzagPath(node->right, result, 0) + 1;
	// Calculate zigzag sequence
	*result = maxValue( *result, maxValue(l, r));
	if (direction == 1)
	{
		// Take the result of right subtree
		return r;
	}
	else
	{
		// Take the result of left subtree
		return l;
	}
}
// Handles the request of find longest pattern of zigzag
void longestZigzag(struct TreeNode *root)
{
	int result = 0;
	if (root != NULL)
	{
		// We consider the sequence
		// 1) left right left ...
		// 2) right left right ...
		zigzagPath(root, & result, 0);
		zigzagPath(root, & result, 1);
	}
	if (result == 0)
	{
		printf(" None \n");
	}
	else
	{
		printf(" Longest zigzag : %d \n", result);
	}
}
int main()
{
	// Define trees
	struct BinaryTree *tree = newTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	     /     / \
	    9     1  -2  
	         /
	        7 
	         \
	          10
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree->root = newNode(1);
	tree->root->left = newNode(2);
	tree->root->right = newNode(3);
	tree->root->left->left = newNode(3);
	tree->root->left->right = newNode(4);
	tree->root->left->right->left = newNode(-7);
	tree->root->left->right->left->left = newNode(9);
	tree->root->right->left = newNode(6);
	tree->root->right->right = newNode(5);
	tree->root->right->left->right = newNode(4);
	tree->root->right->right->right = newNode(2);
	tree->root->right->left->right->left = newNode(1);
	tree->root->right->left->right->right = newNode(-2);
	tree->root->right->left->right->left->left = newNode(7);
	tree->root->right->left->right->left->left->right = newNode(10);
	longestZigzag(tree->root);
	return 0;
}

Output

 Longest zigzag : 4
/*
  Java Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public TreeNode root;
	public int result;
	public BinaryTree()
	{
		this.root = null;
		this.result = 0;
	}
	// Returns the max of given two numbers
	public int maxValue(int l, int r)
	{
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	public int zigzagPath(TreeNode node, boolean direction)
	{
		if (node == null)
		{
			return -1;
		}
		else if (node.left == null && node.right == null)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		int l = zigzagPath(node.left, true) + 1;
		int r = zigzagPath(node.right, false) + 1;
		// Calculate zigzag sequence
		this.result = maxValue(this.result, maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	public void longestZigzag()
	{
		this.result = 0;
		if (this.root != null)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			zigzagPath(this.root, true);
			zigzagPath(this.root, false);
		}
		if (this.result == 0)
		{
			System.out.print(" None \n");
		}
		else
		{
			System.out.print(" Longest zigzag : " + this.result + " \n");
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    3   4 6   5
		       /   \   \
		     -7     4   2
		     /     / \
		    9     1  -2  
		         /
		        7 
		         \
		          10
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.left.left = new TreeNode(3);
		tree.root.left.right = new TreeNode(4);
		tree.root.left.right.left = new TreeNode(-7);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.right.left = new TreeNode(6);
		tree.root.right.right = new TreeNode(5);
		tree.root.right.left.right = new TreeNode(4);
		tree.root.right.right.right = new TreeNode(2);
		tree.root.right.left.right.left = new TreeNode(1);
		tree.root.right.left.right.right = new TreeNode(-2);
		tree.root.right.left.right.left.left = new TreeNode(7);
		tree.root.right.left.right.left.left.right = new TreeNode(10);
		tree.longestZigzag();
	}
}

Output

 Longest zigzag : 4
// Include header file
#include <iostream>
using namespace std;
/*
  C++ Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode
{
	public: int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: TreeNode *root;
	int result;
	BinaryTree()
	{
		this->root = NULL;
		this->result = 0;
	}
	// Returns the max of given two numbers
	int maxValue(int l, int r)
	{
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	int zigzagPath(TreeNode *node, bool direction)
	{
		if (node == NULL)
		{
			return -1;
		}
		else if (node->left == NULL && node->right == NULL)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		int l = this->zigzagPath(node->left, true) + 1;
		int r = this->zigzagPath(node->right, false) + 1;
		// Calculate zigzag sequence
		this->result = this->maxValue(this->result, this->maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	void longestZigzag()
	{
		this->result = 0;
		if (this->root != NULL)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			this->zigzagPath(this->root, true);
			this->zigzagPath(this->root, false);
		}
		if (this->result == 0)
		{
			cout << " None \n";
		}
		else
		{
			cout << " Longest zigzag : " << this->result << " \n";
		}
	}
};
int main()
{
	BinaryTree tree = BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	     /     / \
	    9     1  -2  
	         /
	        7 
	         \
	          10
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree.root = new TreeNode(1);
	tree.root->left = new TreeNode(2);
	tree.root->right = new TreeNode(3);
	tree.root->left->left = new TreeNode(3);
	tree.root->left->right = new TreeNode(4);
	tree.root->left->right->left = new TreeNode(-7);
	tree.root->left->right->left->left = new TreeNode(9);
	tree.root->right->left = new TreeNode(6);
	tree.root->right->right = new TreeNode(5);
	tree.root->right->left->right = new TreeNode(4);
	tree.root->right->right->right = new TreeNode(2);
	tree.root->right->left->right->left = new TreeNode(1);
	tree.root->right->left->right->right = new TreeNode(-2);
	tree.root->right->left->right->left->left = new TreeNode(7);
	tree.root->right->left->right->left->left->right = new TreeNode(10);
	tree.longestZigzag();
	return 0;
}

Output

 Longest zigzag : 4
// Include namespace system
using System;
/*
  C# Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int result;
	public BinaryTree()
	{
		this.root = null;
		this.result = 0;
	}
	// Returns the max of given two numbers
	public int maxValue(int l, int r)
	{
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	public int zigzagPath(TreeNode node, Boolean direction)
	{
		if (node == null)
		{
			return -1;
		}
		else if (node.left == null && node.right == null)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		int l = zigzagPath(node.left, true) + 1;
		int r = zigzagPath(node.right, false) + 1;
		// Calculate zigzag sequence
		this.result = maxValue(this.result, maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	public void longestZigzag()
	{
		this.result = 0;
		if (this.root != null)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			zigzagPath(this.root, true);
			zigzagPath(this.root, false);
		}
		if (this.result == 0)
		{
			Console.Write(" None \n");
		}
		else
		{
			Console.Write(" Longest zigzag : " + this.result + " \n");
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    3   4 6   5
		       /   \   \
		     -7     4   2
		     /     / \
		    9     1  -2  
		         /
		        7 
		         \
		          10
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.left.left = new TreeNode(3);
		tree.root.left.right = new TreeNode(4);
		tree.root.left.right.left = new TreeNode(-7);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.right.left = new TreeNode(6);
		tree.root.right.right = new TreeNode(5);
		tree.root.right.left.right = new TreeNode(4);
		tree.root.right.right.right = new TreeNode(2);
		tree.root.right.left.right.left = new TreeNode(1);
		tree.root.right.left.right.right = new TreeNode(-2);
		tree.root.right.left.right.left.left = new TreeNode(7);
		tree.root.right.left.right.left.left.right = new TreeNode(10);
		tree.longestZigzag();
	}
}

Output

 Longest zigzag : 4
<?php
/*
  Php Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class BinaryTree
{
	public $root;
	public $result;

	function __construct()
	{
		$this->root = null;
		$this->result = 0;
	}
	// Returns the max of given two numbers
	public	function maxValue($l, $r)
	{
		if ($l > $r)
		{
			return $l;
		}
		else
		{
			return $r;
		}
	}
	// Find zigzag Path
	public	function zigzagPath($node, $direction)
	{
		if ($node == null)
		{
			return -1;
		}
		else if ($node->left == null && $node->right == null)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		$l = $this->zigzagPath($node->left, true) + 1;
		$r = $this->zigzagPath($node->right, false) + 1;
		// Calculate zigzag sequence
		$this->result = $this->maxValue($this->result, $this->maxValue($l, $r));
		if ($direction == true)
		{
			// Take the result of right subtree
			return $r;
		}
		else
		{
			// Take the result of left subtree
			return $l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	public	function longestZigzag()
	{
		$this->result = 0;
		if ($this->root != null)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			$this->zigzagPath($this->root, true);
			$this->zigzagPath($this->root, false);
		}
		if ($this->result == 0)
		{
			echo " None \n";
		}
		else
		{
			echo " Longest zigzag : ". $this->result ." \n";
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	     /     / \
	    9     1  -2  
	         /
	        7 
	         \
	          10
	-----------------------
	    Binary Tree
	-----------------------
	*/
	$tree->root = new TreeNode(1);
	$tree->root->left = new TreeNode(2);
	$tree->root->right = new TreeNode(3);
	$tree->root->left->left = new TreeNode(3);
	$tree->root->left->right = new TreeNode(4);
	$tree->root->left->right->left = new TreeNode(-7);
	$tree->root->left->right->left->left = new TreeNode(9);
	$tree->root->right->left = new TreeNode(6);
	$tree->root->right->right = new TreeNode(5);
	$tree->root->right->left->right = new TreeNode(4);
	$tree->root->right->right->right = new TreeNode(2);
	$tree->root->right->left->right->left = new TreeNode(1);
	$tree->root->right->left->right->right = new TreeNode(-2);
	$tree->root->right->left->right->left->left = new TreeNode(7);
	$tree->root->right->left->right->left->left->right = new TreeNode(10);
	$tree->longestZigzag();
}
main();

Output

 Longest zigzag : 4
/*
  Node Js Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	// Returns the max of given two numbers
	maxValue(l, r)
	{
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	zigzagPath(node, direction)
	{
		if (node == null)
		{
			return -1;
		}
		else if (node.left == null && node.right == null)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		var l = this.zigzagPath(node.left, true) + 1;
		var r = this.zigzagPath(node.right, false) + 1;
		// Calculate zigzag sequence
		this.result = this.maxValue(this.result, this.maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	longestZigzag()
	{
		this.result = 0;
		if (this.root != null)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			this.zigzagPath(this.root, true);
			this.zigzagPath(this.root, false);
		}
		if (this.result == 0)
		{
			process.stdout.write(" None \n");
		}
		else
		{
			process.stdout.write(" Longest zigzag : " + this.result + " \n");
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	     /     / \
	    9     1  -2  
	         /
	        7 
	         \
	          10
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(2);
	tree.root.right = new TreeNode(3);
	tree.root.left.left = new TreeNode(3);
	tree.root.left.right = new TreeNode(4);
	tree.root.left.right.left = new TreeNode(-7);
	tree.root.left.right.left.left = new TreeNode(9);
	tree.root.right.left = new TreeNode(6);
	tree.root.right.right = new TreeNode(5);
	tree.root.right.left.right = new TreeNode(4);
	tree.root.right.right.right = new TreeNode(2);
	tree.root.right.left.right.left = new TreeNode(1);
	tree.root.right.left.right.right = new TreeNode(-2);
	tree.root.right.left.right.left.left = new TreeNode(7);
	tree.root.right.left.right.left.left.right = new TreeNode(10);
	tree.longestZigzag();
}
main();

Output

 Longest zigzag : 4
#   Python 3 Program for
#   Longest zig zag path in a binary tree

#  Tree Node
class TreeNode :
	
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	
	def __init__(self) :
		self.root = None
		self.result = 0
	
	#  Returns the max of given two numbers
	def maxValue(self, l, r) :
		if (l > r) :
			return l
		else :
			return r
		
	
	#  Find zigzag Path
	def zigzagPath(self, node, direction) :
		if (node == None) :
			return -1
		
		elif(node.left == None and node.right == None) :
			return 0
		
		#  Recursively visit left and right subtree
		l = self.zigzagPath(node.left, True) + 1
		r = self.zigzagPath(node.right, False) + 1
		#  Calculate zigzag sequence
		self.result = self.maxValue(self.result, self.maxValue(l, r))
		if (direction == True) :
			#  Take the result of right subtree
			return r
		else :
			#  Take the result of left subtree
			return l
		
	
	#  Handles the request of find longest pattern of zigzag
	def longestZigzag(self) :
		self.result = 0
		if (self.root != None) :
			#  We consider the sequence
			#  1) left right left ...
			#  2) right left right ...
			self.zigzagPath(self.root, True)
			self.zigzagPath(self.root, False)
		
		if (self.result == 0) :
			print(" None ")
		else :
			print(" Longest zigzag : ", self.result ," ")
		
	

def main() :
	tree = BinaryTree()
	# 
	#          1
	#        /   \
	#       2     3
	#      / \   / \
	#     3   4 6   5
	#        /   \   \
	#      -7     4   2
	#      /     / \
	#     9     1  -2  
	#          /
	#         7 
	#          \
	#           10
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(2)
	tree.root.right = TreeNode(3)
	tree.root.left.left = TreeNode(3)
	tree.root.left.right = TreeNode(4)
	tree.root.left.right.left = TreeNode(-7)
	tree.root.left.right.left.left = TreeNode(9)
	tree.root.right.left = TreeNode(6)
	tree.root.right.right = TreeNode(5)
	tree.root.right.left.right = TreeNode(4)
	tree.root.right.right.right = TreeNode(2)
	tree.root.right.left.right.left = TreeNode(1)
	tree.root.right.left.right.right = TreeNode(-2)
	tree.root.right.left.right.left.left = TreeNode(7)
	tree.root.right.left.right.left.left.right = TreeNode(10)
	tree.longestZigzag()

if __name__ == "__main__": main()

Output

 Longest zigzag :  4
#   Ruby Program for
#   Longest zig zag path in a binary tree

#  Tree Node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root, :result
	attr_accessor :root, :result
 
	
	def initialize() 
		self.root = nil
		self.result = 0
	end

	#  Returns the max of given two numbers
	def maxValue(l, r) 
		if (l > r) 
			return l
		else 
			return r
		end

	end

	#  Find zigzag Path
	def zigzagPath(node, direction) 
		if (node == nil) 
			return -1
		elsif(node.left == nil && node.right == nil) 
			return 0
		end

		#  Recursively visit left and right subtree
		l = self.zigzagPath(node.left, true) + 1
		r = self.zigzagPath(node.right, false) + 1
		#  Calculate zigzag sequence
		self.result = self.maxValue(self.result, self.maxValue(l, r))
		if (direction == true) 
			#  Take the result of right subtree
			return r
		else 
			#  Take the result of left subtree
			return l
		end

	end

	#  Handles the request of find longest pattern of zigzag
	def longestZigzag() 
		self.result = 0
		if (self.root != nil) 
			#  We consider the sequence
			#  1) left right left ...
			#  2) right left right ...
			self.zigzagPath(self.root, true)
			self.zigzagPath(self.root, false)
		end

		if (self.result == 0) 
			print(" None \n")
		else 
			print(" Longest zigzag : ", self.result ," \n")
		end

	end

end

def main() 
	tree = BinaryTree.new()
	# 
	#          1
	#        /   \
	#       2     3
	#      / \   / \
	#     3   4 6   5
	#        /   \   \
	#      -7     4   2
	#      /     / \
	#     9     1  -2  
	#          /
	#         7 
	#          \
	#           10
	# -----------------------
	#     Binary Tree
	# -----------------------
	
	tree.root = TreeNode.new(1)
	tree.root.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(3)
	tree.root.left.left = TreeNode.new(3)
	tree.root.left.right = TreeNode.new(4)
	tree.root.left.right.left = TreeNode.new(-7)
	tree.root.left.right.left.left = TreeNode.new(9)
	tree.root.right.left = TreeNode.new(6)
	tree.root.right.right = TreeNode.new(5)
	tree.root.right.left.right = TreeNode.new(4)
	tree.root.right.right.right = TreeNode.new(2)
	tree.root.right.left.right.left = TreeNode.new(1)
	tree.root.right.left.right.right = TreeNode.new(-2)
	tree.root.right.left.right.left.left = TreeNode.new(7)
	tree.root.right.left.right.left.left.right = TreeNode.new(10)
	tree.longestZigzag()
end

main()

Output

 Longest zigzag : 4 

/*
  Scala Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: TreeNode , var result: Int)
{
	def this()
	{
		this(null, 0);
	}
	// Returns the max of given two numbers
	def maxValue(l: Int, r: Int): Int = {
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	def zigzagPath(node: TreeNode, direction: Boolean): Int = {
		if (node == null)
		{
			return -1;
		}
		else if (node.left == null && node.right == null)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		var l: Int = this.zigzagPath(node.left, true) + 1;
		var r: Int = this.zigzagPath(node.right, false) + 1;
		// Calculate zigzag sequence
		this.result = this.maxValue(this.result, this.maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	def longestZigzag(): Unit = {
		this.result = 0;
		if (this.root != null)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			this.zigzagPath(this.root, true);
			this.zigzagPath(this.root, false);
		}
		if (this.result == 0)
		{
			print(" None \n");
		}
		else
		{
			print(" Longest zigzag : " + this.result + " \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		         1
		       /   \
		      2     3
		     / \   / \
		    3   4 6   5
		       /   \   \
		     -7     4   2
		     /     / \
		    9     1  -2  
		         /
		        7 
		         \
		          10
		-----------------------
		    Binary Tree
		-----------------------
		*/
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.left.left = new TreeNode(3);
		tree.root.left.right = new TreeNode(4);
		tree.root.left.right.left = new TreeNode(-7);
		tree.root.left.right.left.left = new TreeNode(9);
		tree.root.right.left = new TreeNode(6);
		tree.root.right.right = new TreeNode(5);
		tree.root.right.left.right = new TreeNode(4);
		tree.root.right.right.right = new TreeNode(2);
		tree.root.right.left.right.left = new TreeNode(1);
		tree.root.right.left.right.right = new TreeNode(-2);
		tree.root.right.left.right.left.left = new TreeNode(7);
		tree.root.right.left.right.left.left.right = new TreeNode(10);
		tree.longestZigzag();
	}
}

Output

 Longest zigzag : 4
/*
  Swift 4 Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	var result: Int;
	init()
	{
		self.root = nil;
		self.result = 0;
	}
	// Returns the max of given two numbers
	func maxValue(_ l: Int, _ r: Int)->Int
	{
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	func zigzagPath(_ node: TreeNode? , _ direction : Bool)->Int
	{
		if (node == nil)
		{
			return -1;
		}
		else if (node!.left == nil && node!.right == nil)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		let l: Int = self.zigzagPath(node!.left, true) + 1;
		let r: Int = self.zigzagPath(node!.right, false) + 1;
		// Calculate zigzag sequence
		self.result = self.maxValue(self.result, self.maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	func longestZigzag()
	{
		self.result = 0;
		if (self.root  != nil)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			let _ = self.zigzagPath(self.root, true);
			let _ = self.zigzagPath(self.root, false);
		}
		if (self.result == 0)
		{
			print(" None ");
		}
		else
		{
			print(" Longest zigzag : ", self.result ," ");
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	     /     / \
	    9     1  -2  
	         /
	        7 
	         \
	          10
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree.root = TreeNode(1);
	tree.root!.left = TreeNode(2);
	tree.root!.right = TreeNode(3);
	tree.root!.left!.left = TreeNode(3);
	tree.root!.left!.right = TreeNode(4);
	tree.root!.left!.right!.left = TreeNode(-7);
	tree.root!.left!.right!.left!.left = TreeNode(9);
	tree.root!.right!.left = TreeNode(6);
	tree.root!.right!.right = TreeNode(5);
	tree.root!.right!.left!.right = TreeNode(4);
	tree.root!.right!.right!.right = TreeNode(2);
	tree.root!.right!.left!.right!.left = TreeNode(1);
	tree.root!.right!.left!.right!.right = TreeNode(-2);
	tree.root!.right!.left!.right!.left!.left = TreeNode(7);
	tree.root!.right!.left!.right!.left!.left!.right = TreeNode(10);
	tree.longestZigzag();
}
main();

Output

 Longest zigzag :  4
/*
  Kotlin Program for
  Longest zig zag path in a binary tree
*/
// Tree Node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	var result: Int;
	constructor()
	{
		this.root = null;
		this.result = 0;
	}
	// Returns the max of given two numbers
	fun maxValue(l: Int, r: Int): Int
	{
		if (l > r)
		{
			return l;
		}
		else
		{
			return r;
		}
	}
	// Find zigzag Path
	fun zigzagPath(node: TreeNode ? , direction : Boolean): Int
	{
		if (node == null)
		{
			return -1;
		}
		else if (node.left == null && node.right == null)
		{
			return 0;
		}
		// Recursively visit left and right subtree
		var l: Int = this.zigzagPath(node.left, true) + 1;
		var r: Int = this.zigzagPath(node.right, false) + 1;
		// Calculate zigzag sequence
		this.result = this.maxValue(this.result, this.maxValue(l, r));
		if (direction == true)
		{
			// Take the result of right subtree
			return r;
		}
		else
		{
			// Take the result of left subtree
			return l;
		}
	}
	// Handles the request of find longest pattern of zigzag
	fun longestZigzag(): Unit
	{
		this.result = 0;
		if (this.root != null)
		{
			// We consider the sequence
			// 1) left right left ...
			// 2) right left right ...
			this.zigzagPath(this.root, true);
			this.zigzagPath(this.root, false);
		}
		if (this.result == 0)
		{
			print(" None \n");
		}
		else
		{
			print(" Longest zigzag : " + this.result + " \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var tree: BinaryTree = BinaryTree();
	/*
	         1
	       /   \
	      2     3
	     / \   / \
	    3   4 6   5
	       /   \   \
	     -7     4   2
	     /     / \
	    9     1  -2  
	         /
	        7 
	         \
	          10
	-----------------------
	    Binary Tree
	-----------------------
	*/
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(2);
	tree.root?.right = TreeNode(3);
	tree.root?.left?.left = TreeNode(3);
	tree.root?.left?.right = TreeNode(4);
	tree.root?.left?.right?.left = TreeNode(-7);
	tree.root?.left?.right?.left?.left = TreeNode(9);
	tree.root?.right?.left = TreeNode(6);
	tree.root?.right?.right = TreeNode(5);
	tree.root?.right?.left?.right = TreeNode(4);
	tree.root?.right?.right?.right = TreeNode(2);
	tree.root?.right?.left?.right?.left = TreeNode(1);
	tree.root?.right?.left?.right?.right = TreeNode(-2);
	tree.root?.right?.left?.right?.left?.left = TreeNode(7);
	tree.root?.right?.left?.right?.left?.left?.right = TreeNode(10);
	tree.longestZigzag();
}

Output

 Longest zigzag : 4

Resultant Output Explanation

In the given code, the binary tree is constructed, and the longestZigzag function is called with the root of the tree. The code finds the longest zigzag path length, which is 4 in this case (3 → 4 → -7 → 9).

Time Complexity

The time complexity of the provided solution is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the depth-first traversal. The zigzagPath function performs constant-time operations for each node. Therefore, the overall time complexity is linear in the number of nodes.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post