Question
I have to print the nodes of a binary tree using level order traversal but in spiral form i.e nodes at different level should be printed in spiral form.
for eg: If the tree look like:
The output should be 10 5 20 25 15 6 4.
The algorithm i used is simple and is just a small variation of level order traversal. I just took a variable p.if the variable is equal to 1 than print the order at a given level left to right , if it is -1 print right to left.
https://stackoverflow.com/questions/17485773
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianvoid getlevel(struct node *root,int n,int p)
{
if(root==NULL)
return;
if(n==0)
{
printf("%d ",root->info);
return;
}
if(n>0)
{
if(p==1)
{
getlevel(root->left,n-1,p);
getlevel(root->right,n-1,p);
}
if(p==-1)
{
getlevel(root->right,n-1,p);
getlevel(root->left,n-1,p);
}
}
}
I am getting the answer but the worst case complexity is probably O(n^2) in case of skewed tree.
Can there be a better algorithm for this task?..
My entire program is here
Solution
Yes.
You can do something similar to normal level order traversal.
You have to use two stacks
Start from the root node. Store it's children in one stack. In every iteration, you have nodes of one level in one of the stacks. Print the nodes, and push nodes of next level in other stack. Repeat until your reach the final level.
Time Complexity O(n) and space complexity O(n).
OTHER TIPS
Psuedocode for spiral level order traversal of a binary tree.
//Define two stacks S1, S2
//At each level,
// S1 carries the nodes to be traversed in that level
// S2 carries the child nodes of the nodes in S1
spiralLevelOrder(root) {
S1 = new Stack()
S2 = new Stack()
S1.push(root)
spiralLevelOrderRecursion(S1, S2, 1)
}
spiralLevelOrderRecursion(S1, S2, level) {
while(S1 not empty) {
node = S1.pop()
visit(node)
if (level is odd) {
S2.push(node.rightNode)
S2.push(node.leftNode)
}
else {
S2.push(node.leftNode)
S2.push(node.rightNode)
}
}
if (S2 not empty)
spiralLevelOrderRecursion(S2, S1, level+1)
}
Sample tree : 1-(2-(4,5),3-(5,6)) format : root-(leftchild, rightchild)
Applying the pseudocode :
spiralLevelOrderRecursion([1], [], 1)
S2 - [] -> [3] -> [2, 3]
visit order : 1
spiralLevelOrderRecursion([2,3], [], 2)
S2 - [] -> [4] -> [5,4] -> [6, 5, 4] -> [7, 6, 5, 4]
visit order : 2, 3
spiralLevelOrderRecursion([7,6,5,4], [], 3)
visit order : 7, 6, 5, 4
The following code will do the job :
Language Used : Java
// Algorithm for printing nodes in Zigzag order(zigzag tree traversal)
static void zigzagTreeTraversal(Node root)
{
int count=0,c=1,i=0;
boolean odd=false;
Queue<Node> queue=new LinkedList<Node>();
Node temp = null;
queue.add(root);
System.out.print("Printing Tree Traversal in Zigzag form :");
while(true)
{
if(queue.isEmpty())
{
break;
}
for(i=0;i<c;i++)
{
temp=queue.remove();
System.out.print(", " + temp.data);
if(odd)
{
if(temp.right!=null)
{
queue.add(temp.right);
count++;
}
if(temp.left!=null)
{
queue.add(temp.left);
count++;
}
}
else
{
if(temp.left!=null)
{
queue.add(temp.left);
count++;
}
if(temp.right!=null)
{
queue.add(temp.right);
count++;
}
}
}
c=count;
count=0;
odd=!odd;
}
}
I believe the simplest of them all without any variable just two stacks.
public void zigzagNew() {
TreeNode t = this.root;
Stack<TreeNode> cs = new Stack<>();
Stack<TreeNode> ns = new Stack<>();
cs.add(t);
while(cs.isEmpty()==false || ns.isEmpty() == false) {
while(cs.isEmpty() == false) {
TreeNode cur = cs.pop();
System.out.print(cur.val + " ");
if(cur.left != null) {
ns.push(cur.left);
}
if(cur.right != null) {
ns.push(cur.right);
}
}
System.out.println();
while(ns.isEmpty()==false) {
TreeNode cur = ns.pop();
System.out.print(cur.val + " ");
if(cur.right != null) {
cs.push(cur.right);
}
if(cur.left != null) {
cs.push(cur.left);
}
}
System.out.println();
}
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
public class ZigZagTraversal {
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTree bt = new BinaryTree();
int[] array = {2,5,1,3,11,7,8,9,4,10,6};
/*
* 2
* / \
* / \
* / \
* 5 1
* / \ / \
* / \ / \
* 3 11 7 8
* / \ / \
* 9 4 10 6
*
* */
bt=BinaryTree.buildATree(bt, array);
//BinaryTree.inOrderTraversal(bt);
zigZagTraversal(llForAllNodesAtEachDepth(bt));
zigZagDisplay(bt);
}
public static void zigZagDisplay(BinaryTree bt){
Stack<BinaryTree> s = new Stack<>();
if(s.isEmpty())
s.push(bt);
boolean flag = true;
while(!s.isEmpty()){
Stack<BinaryTree> temp = new Stack<>();
while(!s.isEmpty()){
BinaryTree b = s.pop();
System.out.print(b.data+" ");
if(flag){
if(b.left!=null)
temp.push(b.left);
if(b.right!=null)
temp.push(b.right);
}
else{
if(b.right!=null)
temp.push(b.right);
if(b.left!=null)
temp.push(b.left);
}
}
s=temp;
flag=!flag;
}
}
public static ArrayList<LinkedList<BinaryTree>> llForAllNodesAtEachDepth(BinaryTree bt){
ArrayList<LinkedList<BinaryTree>> res = new ArrayList<LinkedList<BinaryTree>>();
return createLlForAllNodesAtEachDepth(res,bt, 0);
}
public static ArrayList<LinkedList<BinaryTree>> createLlForAllNodesAtEachDepth(ArrayList<LinkedList<BinaryTree>> res, BinaryTree bt, int level){
if(bt==null)
return null;
if(level==res.size()){
LinkedList<BinaryTree> list = new LinkedList<BinaryTree>();
list.add(bt);
res.add(list);
createLlForAllNodesAtEachDepth(res,bt.left,level+1);
createLlForAllNodesAtEachDepth(res,bt.right,level+1);
}
else{
res.get(level).add(bt);
createLlForAllNodesAtEachDepth(res,bt.left,level+1);
createLlForAllNodesAtEachDepth(res,bt.right,level+1);
}
return res;
}
public static void zigZagTraversal(ArrayList<LinkedList<BinaryTree>> res){
boolean flag=true;
for(int i=0;i<res.size();i++){
LinkedList<BinaryTree> temp = res.get(i);
if(flag){
for(int j=0;j<temp.size();j++){
System.out.print(temp.get(j).data+" -> ");
}
flag=false;
}
else{
for(int j=temp.size()-1;j>=0;j--){
System.out.print(temp.get(j).data+" -> ");
}
flag=true;
}
System.out.println();
}
}
}
// simple c++ code using two stacks
<pre> void zigzag(struct node *root)
{
int lefttoright = 1 ;
struct node *temp ;
if(root == NULL)
return ;
stack<struct node *> current , next ,temp2 ;// temp is used to swap
////current and next
current.push(root);
while(!current.empty())
{temp = current.top();
current.pop();
cout<< temp->data << " " ;
if(lefttoright)
{ if(temp->left)
next.push(temp->left) ;
if(temp->right)
next.push(temp->right) ;
}
else
{if(temp->right)
next.push(temp->right) ;
if(temp->left)
next.push(temp->left) ;
}
if(current.empty()) // make current as next and next as current
//to hold next level nodes
{lefttoright = 1-lefttoright ;
temp2 = current ;
current = next ;
next = temp2 ;
}
}
</pre>