CareerCup

Why not do a level order traversal?

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Tree {

	public static ArrayList<TreeNode> getExtremeNodes(TreeNode root) {
		
		ArrayList<TreeNode> result = new ArrayList<TreeNode>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		
		int expectedCurrentLevel = 1, expectedNextLevel = 0;
		int nodesCurrentLevel = 0;
		queue.add(root);
		
		while (!queue.isEmpty()) {
			
			TreeNode node = queue.poll();
			nodesCurrentLevel++;
			
			if (node.left != null) {
				queue.add(node.left);
				expectedNextLevel++;
			}
			if (node.right != null) {
				queue.add(node.right);
				expectedNextLevel++;
			}
			
			if (nodesCurrentLevel == 1 && nodesCurrentLevel != expectedCurrentLevel) 
				result.add(node);
			else if (nodesCurrentLevel == expectedCurrentLevel) {
				result.add(node);
				nodesCurrentLevel = 0;
				expectedCurrentLevel = expectedNextLevel;
				expectedNextLevel = 0;
			}
			
		}
		
		return result;
	}

}

public class TreeNode {

	public int data;
	public TreeNode left;
	public TreeNode right;
	
}

We can send an argument to indicate whether leftmost has to printed or the rightmost has to be printed. Nodes data will be printed if its lefts turn and the node is left most or if its not lefts turn and the node is right most node.

Also we need to handle a case where a node is leftMost node at that level but it doesnot have a left child, so the right child will become the leftmost, similarly for the rightMost case.

class Node {
	Node right;
	Node left;
	int data;
   }

public static void printAlternateCorner(Node node,boolean leftMost,boolean rightMost,boolean left){

            if(node==null){
		return;
	    }
	   
            if(left){
		if(leftMost)	
                {
			System.out.println(node.data);
 		}

	    }else{
		if(rightMost){
			System.out.println(node.data);
		}
	   }
	   left=!left; 

	   printAlternateCorner(node.left,leftMost, (rightMost && node.right == null),left);
	   printAlternateCorner(node.right,(leftMost && node.left==null), rightMost,left);
	   							
}

public static void main(String[] args){
	Node root;
	/* Initialize the tree */
	Sytem.out.println(root.data);
	printAlternateCorner(root.left,true,false,false);
	printAlternateCorner(root.right,false,true,false);
}

it is same as printing the first nodes in zig zag order .....

This can be easily solved using Zig-Zag level order traversal of the given tree.Use 2 stacks to do the zig zig level order traversal.

For More detail explanation just google "leetcode : printing-binary-tree-in-zig-zag-level".
Below is a small working code for the same. TreeNode represents our Tree.

void printExtremeNodes(TreeNode root) {
		if (root == null)
			return;

		Stack<TreeNode> stack1 = new Stack<TreeNode>();
		Stack<TreeNode> stack2 = new Stack<TreeNode>();
		Stack<TreeNode> tempStack = null;
		stack1.push(root);
		TreeNode temp = null, left, right;
		int i = 0, level = 0;
		while (!stack1.isEmpty()) {
			i = 0;
			while (!stack1.isEmpty()) {
				temp = stack1.pop();
				if (i == 0)
					System.out.println(temp.data);
				left = temp.left;
				right = temp.right;
				if (level % 2 == 0) {
					if (left != null)
						stack2.push(left);
if(right!=null)					
stack2.push(right);
				} else {
					if (right != null)
						stack2.push(right);
					if (left != null)
						stack2.push(left);
				}
				++i;
			}
			tempStack = stack1;
			stack1 = stack2;
			stack2 = tempStack;
			++level;
		}

	}

Shall we consider the root as one of the extremes ...if yes then left extreme or right extreme?

void alternative_traverse(Node root){
	if (root == null)
		return;
	System.out.println(root.content);
	Node right = current.right;
	Node left = current.left;
	boolean left_round = false;
	while (left != null && right != null){
		if (left_round){
			System.out.println(left.content);
			left_round = false;
			left = left.left;
		}else{
			System.out.println(right.content);
			left_round = true;
			right = right.right;
		}
	}
	while (right != null){
		System.out.println(right.content);
		right = right.right;
	}
	while (left != null){
		System.out.println(left.content);
		left = left.left;
	}
	return;
}

Hi..Here is my solution..but before using this function print the root node and then call its left child and right child in the main function

void print_Alternate(tree_node *node1,tree_node *node2,int count)
{
    tree_node *child1=NULL,*child2=NULL;

    if(node1==NULL&&node2==NULL)
    return ;
    if(!node1&&node2)
    {
        printf("hi");
        printf("%d ",node2->data);
        if(node2->right)
        print_Alternate(node1,node2->right,++count%2);
        else
        print_Alternate(node1,node2->left,++count%2);


    }
     if(!node2&&node1)
    {
         printf("hello");
        printf("%d ",node1->data);
        if(node1->left)
        print_Alternate(node1->left,node2,++count%2);
        else
        print_Alternate(node1->right,node2,++count%2);

    }

    if(count==1)
    {

        printf("%d ",node2->data);
        if(node1->left)
        child1=node1->left;
        else
        child1=node1->right;
        if(node2->right)
        child2=node2->right;
        else
        child2=node2->left;
        print_Alternate(child1,child2,++count%2);

    }
    else
    {
        printf("%d ",node1->data);
        if(node1->left)
        child1=node1->left;
        else if(node1->right)
        child1=node1->right;

        if(node2->right)
        child2=node2->right;
        else
        child2=node2->left;

        print_Alternate(child1,child2,++count%2);
    }
}

}

import java.util.*;
import java.io.*;

class Node {
	public int data;
	public Node left;
	public Node right;
	
	Node(int data){
		this.data = data;
	}
}

class LevelNode extends Node{
	int level;
	
	LevelNode(int data, int level)
	{
		super(data);
		this.level = level;
	}
}


class BFS{
	public Queue<LevelNode> q;
	private Node root;
	
	BFS(){
		this.buildTree();
		this.processBF();
	}
	
	public Iterable<Integer> getPiers()
	{
		LevelNode oldNode = null;
		List<Integer> list = new ArrayList<Integer>();
		for(LevelNode node : this.q)
		{
			if (oldNode != null)
			{	
				if (node.level != oldNode.level){
					list.add(oldNode.data);
					list.add(node.data);
				}
			}
			oldNode = node;
		}
		list.add(oldNode.data); // The very last one is also a pier
		return list;
	}
	
	private void processBF()
	{
		if (root == null)
			return;
		
		q = new LinkedList<LevelNode>();
		q.add(new LevelNode(root.data, 0));
		process(root, 1);
	}
	
	private void process(Node node, int level)
	{
		if (node == null)
			return;
		
		if (node.left != null)
			q.add(new LevelNode(node.left.data, level));
		if (node.right != null)
			q.add(new LevelNode(node.right.data, level));
		process(node.left, level+1);
		process(node.right, level+1);
	}
	
	private void buildTree()
	{
		root = new Node(0);
		root.left = new Node(1);
		root.right = new Node(2);
		root.left.left = new Node(3);
		root.left.right = new Node(4);
		root.right.left = new Node(5);
		root.right.right = new Node(6);
		
		root.right.left.left = new Node(7);
		root.right.left.right = new Node(8);
		root.right.right.left = new Node(9);
		root.right.right.right = new Node(10);
	}
	
	public static void main(){		
	}
}

-Have an array to hold tree node pointers
-copy root pointer at mid point of into array
-------------10-------------------------
-now replace existing tree node with its left and right if exists
--------------5-11---------------------
-again replace existing tree node with its left and right if exists
--------------9-20-15-------------------
--------------14-25----------------------
-----------------30------------------------
-at each steps we can print tree node info value alternately

can we do it in O(n) complexity and without using extra memory?

public void PrintNodesInZipZag(Node root)
{
	if(root == null)
		return;

	bool levelPrinted = false;
	int level = 1;
	Node levelBreak = new Node();
	levelBreak.Value = null;
	Node temp = null;
	
	Queue q = new Queue();
	q.enqueue(root);
	q.enqueue(levelBreak);
	
	while (q.Count > 0)
	{
		temp = q.Dequeue();
		if(temp.Left != null) q.Enqueue(temp.Left);
		if(temp.Right != null) q.Enqueue(temp.Right);
		
		if (level % 2 == 1 && !levelPrinted)
		{
			Console.Write(temp.Value);
			levelPrinted = true;
		}
		else
		{
			if (temp.Value == null)
			{
				Console.Write(lastValue);
				level++;
				q.enqueue(levelBreak);
			}
		}
		
		lastValue = temp.Value;
	}
}

Took me awhile to figure out that it was a Binary Tree and not a Binary Search Tree... irregardless, the solution works for both.

package amazon;

import java.util.LinkedList;

public class BSTCorners {
	public static void main(String[] args) {
		BSTCorners bst = new BSTCorners();
		bst.insertTestData();
		bst.print();
	}

	private Node _root;

	public void print() {
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.add(_root);

		int direction = 1;
		int level = -1;
		while (!queue.isEmpty()) {
			Node n = queue.poll();

			if (n.getLeft() != null)
				queue.add(n.getLeft());

			if (n.getRight() != null)
				queue.add(n.getRight());

			if (level == -1) {
				System.out.println("START: " + n);
				level = n.getLevel();
			} else if (direction == 0 && level < n.getLevel()) {
				System.out.println("LEFT: " + n);
				level = n.getLevel();
				direction = 1;
			} else if (direction == 1 && level < n.getLevel() && (queue.peek() == null || queue.peek().getLevel() > n.getLevel())) {
				System.out.println("RIGHT: " + n);
				level = n.getLevel();
				direction = 0;
			}
		}
	}

	public void insertTestData() {
		_root = new Node(10);
		Node n5 = new Node(5);
		Node n11 = new Node(11);
		Node n9 = new Node(9);
		Node n20 = new Node(20);
		Node n15 = new Node(15);
		Node n14 = new Node(14);
		Node n25 = new Node(25);
		Node n30 = new Node(30);

		_root.setLeft(n5);
		_root.setRight(n11);
		
		n5.setLeft(n9);
		n5.setRight(n20);

		n9.setLeft(n14);

		n11.setRight(n15);

		n15.setLeft(n25);

		n25.setRight(n30);
	}

	public static class Node {
		private int _level;
		private int _weight;
		private Node _left;
		private Node _right;

		public Node(int weight) { _weight = weight;	}
		public int getLevel() {	return _level;	}
		public void setLevel(int level) {_level = level;}
		public Node getLeft() {	return _left;}
		public Node getRight() {return _right;}
		public int getWeight() {return _weight;	}
		public String toString() { return "W:" + _weight + ",L:" + _level;}
		
		public void setLeft(Node left) {
			left.setLevel(_level + 1);
			_left = left;
		}

		public void setRight(Node right) {
			right.setLevel(_level + 1);
			_right = right;
		}
	}
}

I think it is better to think about it as BFS. I got the level in each iteration in a queue.
I use alternating "left" variable to view the first element in the leve; queue one time(left most), and last element the other time ( right most)

private static void PrintAlternating(TreeNode<int> root)
        {
            if (root == null)
                return;
            Queue<TreeNode<int>> level = new Queue<TreeNode<int>>();
            level.Enqueue(root);
            bool left = true;
            TreeNode<int> element2Print;
            while (level.Count > 0)
            {
                Queue<TreeNode<int>> newLevel = new Queue<TreeNode<int>>();
                element2Print = level.Peek();
                while (level.Count > 0)
                {
                    if (!left)
                        element2Print = level.Peek();
                    TreeNode<int> current = level.Dequeue();
                    if (current.left != null)
                        newLevel.Enqueue(current.left);
                    if (current.right != null)
                        newLevel.Enqueue(current.right);
                }
                Console.WriteLine(element2Print.value);
                level = new Queue<TreeNode<int>>(newLevel.ToArray());
                left = !left;
            }

        }

TESTING

static void Main(string[] args)
        {
            TreeNode<int> root = InitiateTree();
            PrintAlternating(root);
            Console.ReadKey();
        }

 public class TreeNode<T>
    {

        public TreeNode(T value, TreeNode<T> left, TreeNode<T> right)
        {
            this.value = value;
            this.left = left;
            this.right = right;

        }

        public T value;
        public TreeNode<T> left;
        public TreeNode<T> right;

    }
        private static TreeNode<int> InitiateTree()
        {
            return new TreeNode<int>(1,
                new TreeNode<int>(2,
                    null,
                    new TreeNode<int>(4,
                        null,
                        null)),
                new TreeNode<int>(3,
                     new TreeNode<int>(5,
                         new TreeNode<int>(7,
                             null,
                             null),
                             null
                                       ),
                     new TreeNode<int>(6,
                             null,
                             null)
                                 )
                                                    );
        }

public void printAlternateCorners(Node root){
		//working phase
		Node p,q;
		p=root;			//traverses the left side 
		q=root.right;		//traverse the right side 
		
		System.out.println(""+p.info);
		System.out.println(""+q.info);
		
		while(p!=null || q != null){
			
			//first traverse the left side 
			if(p!=null){
				for(int i=0;i<2;i++){
					if(p.left != null){
						p=p.left;
						i++;
					}else if(p.right != null){
						p=p.right;
					}else{
						p = null;
						i=2;//terminate the loop 
					}					
				}
			}
			
			if(p!=null)
			System.out.println(""+p.info);
			
			//first traverse the left side 
			if(q!=null){
				for(int i=0;i<2;i++){
					if(q.right != null){
						q=q.right;
						i++;
					}else if(q.left != null){
						q=q.left;
					}else{
						q = null;
						i=2;//terminate the loop 
					}					
				}
			}
			System.out.println(""+q.info);
			
		}
		
		
	}

void ZigZacTraversal(struct btree *root)
{
struct btree *Stack1[20],*Stack2[20],*temp;
int top1=-1,top2=-1,LeftToRight=1;
int flag1=0,flag=0;

Stack1[++top1]=root;

while(top1>=0 || top2>=0)
{
if(LeftToRight)
{
while(top1>=0)
{
temp=Stack1[top1--];
if(flag==0){printf("%d ",temp->data); flag=1;}

if(temp->right)
Stack2[++top2]=temp->right;
if(temp->left)
Stack2[++top2]=temp->left;



}
printf("|");
flag=0;
}
else
{
while(top2>=0)
{
temp=Stack2[top2--];
if(flag1==0){printf("%d ",temp->data); flag1=1;}

if(temp->left)
Stack1[++top1]=temp->left;

if(temp->right)
Stack1[++top1]=temp->right;
}
printf("|");
flag1=0;
}
LeftToRight=1-LeftToRight;
}
}

void ZigZacTraversal(struct btree *root)
{
    struct btree *Stack1[20],*Stack2[20],*temp;
    int top1=-1,top2=-1,LeftToRight=1;
    int flag1=0,flag=0;
     
    Stack1[++top1]=root;
     
    while(top1>=0 || top2>=0)
    {
        if(LeftToRight)
        {
            while(top1>=0)
            {
                temp=Stack1[top1--]; 
                if(flag==0){printf("%d ",temp->data); flag=1;}
                 
                if(temp->left)
                    Stack2[++top2]=temp->left;
                     
                if(temp->right)
                    Stack2[++top2]=temp->right;
            }
            printf("|");
            flag=0;
        }
        else
        {
            while(top2>=0)
            {
                temp=Stack2[top2--];
                if(flag1==0){printf("%d ",temp->data); flag1=1;}
                 
                if(temp->right)
                    Stack1[++top1]=temp->right;
                     
                if(temp->left)
                    Stack1[++top1]=temp->left;
            }
            printf("|");
            flag1=0;
        }
        LeftToRight=1-LeftToRight;
    }
}

void print_alternate(node* root)
{
	queue<node*&> nodes;
	nodes.enqueue(root);
	bool printLeft = true;

	while(!nodes.empty())
	{
		vector<node*&> temp;
		while(!nodes.empty())
		{
			temp.push_back(nodes.dequeue());
		}
	
		if(printLeft) cout << temp[0];
		else cout << temp[temp.size() - 1];
	
		printLeft = ~printLeft;

		for(size_t i = 0; i < temp.size(); ++i)
		{
			const node*& front = nodes.dequeue();
			if(front->left != NULL) nodes.enqueue(front->left);
			if(front->right != NULL) nodes.enqueue(front->right);
		}
	}	
}

public static void printEdgesInAlternateOrder(Node<?> root) {
    printNode(root);
    Node<?> right = root.right();
    Node<?> left = root.left();
    boolean printLeft = false;

    while (right != null || left != null) {
      if (right != null) {
        if (!printLeft) {
          printNode(right);
        }
        right = right.right() != null ? right.right() : right.left();
      }
      if (left != null) {
        if (printLeft) {
          printNode(left);
        }
        left = left.left() != null ? left.left() : left.right();
      }

      printLeft = !printLeft;
    }
  }

  private static void printNode(Node<?> root) {
    System.out.print(root.value() + " ");
  }

Recursive and iterative versions written in Groovy. Both are O(n), but iterative is more efficient because there is less overhead.

def "should solve the problem"() {
		given:
		def tree = n(10, n(5, n(9, n(14), null), n(20)), n(11, null, n(15, null, n(25, null, n(30)))))
		
		when:
		def resultRecursive = extremeNodesInAlternateOrderRecursive(tree)
		def resultIterative = extremeNodesInAlternateOrderIterative(tree)
		
		then:
		resultRecursive == [10, 11, 15, 25, 30]
		resultIterative == [10, 11, 15, 25, 30]
	}
	
	static class Node {
		def value
		Node left
		Node right
		
		public String toString() {
			"$value:{$left, $right}"
		}
	}
	
	static Node n(value, left, right) {
		return new Node(value:value, left:left, right:right)
	}
	
	static Node n(value) {
		return new Node(value:value)
	}

	def extremeNodesInAlternateOrderRecursive(tree) {
		def level_values = []
		
		extremeNodesInAlternateOrderRecursive(tree, 0, level_values)
		
		return level_values
	}
	
	def extremeNodesInAlternateOrderRecursive(node, level, level_values) {
		if(!node) {
			return
		}
		
		// even levels should return the leftmost element
		// odd levels should return rightmost element
		def even = level%2 == 0
		
		// only add the element in case it is the first of that level
		if(even && level_values.size() <= level) {
			level_values << node.value
		} else {
			if(level_values.size() <= level) {
				level_values << node.value
			} else {
				level_values[level] = node.value
			}
		}
		
		extremeNodesInAlternateOrderRecursive(node.left, level+1, level_values)
		extremeNodesInAlternateOrderRecursive(node.right, level+1, level_values)
	}
	
	
	def extremeNodesInAlternateOrderIterative(tree) {
		def level_values = []
		
		def nodeQueue = [tree]		// nodes found in breadth-first 
		def levelQueue = [0]	// level of the nodes in the nodeQueue
		
		def i = 0
		while(i < nodeQueue.size()) {
			def node = nodeQueue[i]
			def level = levelQueue[i]
			
			// even levels should return the leftmost element
			// odd levels should return rightmost element
			def even = level%2 == 0
		
			// only add the element in case it is the first of that level
			if(even && level_values.size() <= level) {
				level_values << node.value
			} else {
				if(level_values.size() <= level) {
					level_values << node.value
				} else {
					level_values[level] = node.value
				}
			}
		
			if(node.left) {
				nodeQueue << node.left
				levelQueue << level+1
			}
			
			if(node.right) {
				nodeQueue << node.right
				levelQueue << level+1
			}
			
			i++
		}
		
		return level_values
	}

void display_opposite_corner(BSTNode* root)
{
if(!root) return;
cout<<root->key<<endl;
int iCount=0;
BSTNode* tempRight=root;
BSTNode* tempLeft=root;
while(iCount>=0 && tempRight->right && tempLeft->left)
{
tempLeft=tempLeft->left;
tempRight=tempRight->right;
if(iCount%2!=0)
{
cout<<tempLeft->key<<endl;
}
else
{
cout<<tempRight->key<<endl;
}
iCount++;
}
while(tempRight->right)
{
tempRight= tempRight->right;
cout<<tempRight->key<<endl;

}
while(tempLeft->left)
{
tempLeft=tempLeft->left;
cout<<tempLeft->key<<endl;

}


}

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

/*declaration of the node structure of binary tree*/
struct node
{
int data;
struct node *left, *right;
};

//declare these two variable as a static for safer side
static int checkleftmost=0, countNode=0, LeftmostNode=0, RightmostNode=0;

/*Function to return height of binary tree*/
int TreeHeight(struct node *tree)
{
int Lheight=0, Rheight=0;

//base condition
if(NULL == tree)
return 0;

Lheight = TreeHeight(tree->left);
Rheight = TreeHeight(tree->right);

if(Lheight > Rheight)
return Lheight+1;
else
return Rheight+1;
}

/*Function to print the all the node on given level of binary tree*/
void printGivenLevel(struct node *tree, int level)
{
//base condition1 to return if null
if( NULL == tree )
return;

//hold each data of tree node so that we can retain the last call to print rightmost node of level
//note- at this point current node i.e. tree will not be NULL so update the RightmostNode here only.
RightmostNode = tree->data;

//base condition2 - to print the node at givel level
if( 1 == level )
{
//count the node at givel level
countNode++;

//print the left most node of this level
if( 1 == checkleftmost )
{
LeftmostNode = tree->data;
checkleftmost = 0;
}
}
else if (level > 1)
{
printGivenLevel(tree->left, level-1);
printGivenLevel(tree->right, level-1);
}
}

/*Function to print the level order traversal of binary tree*/
void printLevelOrder(struct node *root)
{
int height=0, itr;

height = TreeHeight(root);

for( itr=1; itr<=height; itr++)
{
//set the variable to print the lest most node
checkleftmost = 1;

printGivenLevel(root,itr);

if( 1 == itr%2 )
{
printf("%d ",LeftmostNode);
}
else if( 0 == itr%2 )
{
//countNode is used to print right most node if level consist single node.
//if level contains single node then this condition is to avoid printing of duplicate node.
//Note- assuming this program will not be having single node in any level except level 1 i.e. root node.
if( countNode > 1 )
{
//print the rightmost node
printf("%d ",RightmostNode);

}
}

//reset all the variable for the this pass
LeftmostNode = 0;
RightmostNode = 0;
countNode = 0;
}
}

/*utility function to create binary tree*/
struct node* newNode(int data)
{
struct node *temp = (struct node*) malloc ( sizeof(struct node) );

temp->data = data;
temp->left = temp->right = NULL;
}

/*Main function to check functionality*/
int main()
{
struct node *root = newNode(3);
root->left = newNode(4);
root->left->left = newNode(7);
root->left->left->right = newNode(22);
root->left->right = newNode(9);
root->left->right->right = newNode(14);
root->right = newNode(20);
root->right->left = newNode(11);
root->right->left->left = newNode(30);
root->right->left->right = newNode(25);
root->right->left->right->left = newNode(27);
root->right->left->right->right = newNode(90);
//root->right->left->right->right->left = newNode(31);

printLevelOrder(root);

getch();
return 0;
}

I've managed to do it using only one queue and one dictionary (using JavaScript).

If we use the queue to do the tree traversal and the dictionary indexed by the current height containing a list of nodes on each height, the first node of each list will be the leftmost one and the last node will be the rightmost.

So we can just:

const solve = (node) => {
  const nodesPerHeight = {};
  const queue = [{ node, height: 0 }];
  while (queue.length > 0) {
    const { node, height } = queue.shift();

    if (!nodesPerHeight[height]) {
      nodesPerHeight[height] = [node];
    } else {
      nodesPerHeight[height].push(node);
    }

    if (node.left) {
      queue.push({ node: node.left, height: height + 1 });
    }

    if (node.right) {
      queue.push({ node: node.right, height: height + 1 });
    }
  }

  for (let height of Object.keys(nodesPerHeight)) {
    if (parseInt(height) % 2 == 0) {
      console.log(nodesPerHeight[height].shift().value);
    } else {
      console.log(nodesPerHeight[height].pop().value);
    }
  }
};