$/**$

This method determines if a BST forms a zig$-$zag pattern. By this we mean

that each node has exactly one child, except for the leaf. In addition,

the nodes alternate between being a left and a right child. An empty tree

or a tree consisting of just the root are both said to form a zigzag

pattern. For example, if you insert the elements $10,5,9,6,7$ into a

BST in that order. $,$ you will get a zig$-$zag.

@return True if the tree forms a zigzag and false otherwise.

$*/$

public boolean isZigZag$()\{$

$//$ TODO: $4$ Write this.

if$($root $==$ NULL$\_$NODE $||$

$($root$.$left $==$ NULL$\_$NODE && root.right $==$ NULL$\_$NODE$))\{$

$\}$

return true;

Node orgroot $=$ root;

$//$ if$($root$.$left $!=$ NULL$\_$NODE && root.right $!=$ NULL$\_$NODE$)\{$

$//\}$

return false;

Node temp $=$ root.right;

root $=$ root.left;

if$($root $!=$ NULL$\_$NODE$)\{$

isZigZag$()$;

$\}$

boolean zigzagLeft $=$ isZigZag$()$;

root $=$ temp;

boolean zigzagRight $=$ isZigZag$()$;

root $=$ orgroot;

$\}$

return zigzagLeft$||$igzagRight;

public void insert$($T e$)\{$

$\}$