# Longest zig zag path in a binary tree

Here given code implementation process.

``````/*
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_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_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``

## 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.