Amazon Interview Question for SDE-2s


Team: Marketplace
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

i think we should use breadth first search

- Anonymous December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bfs

- anaonymousgeek December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n = Node('A', Node('B', Node('D'), Node('E')), Node('C', Node('F')))

q = deque()
q.append(n)

num_current_level = 1
num_next_level = 0

while q:
    node = q.popleft()
    num_current_level -= 1

    if not q or not num_current_level:
        node.neighbor = Node('None')
    else:
        node.neighbor = q[0]

    print '%s: %s' % (node.value, node.neighbor.value)

    if node.left:
        q.append(node.left)
        num_next_level += 1

    if node.right:
        q.append(node.right)
        num_next_level += 1

    if not num_current_level:
        num_current_level = num_next_level
        num_next_level = 0

- supatroopa December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS using C#:

public void AssignNeighbor(Node root)
        {

            List<Node> current = new List<Node>();
            current.Add(root);

            while (current.Count > 0)
            {
                List<Node> children = new List<Node>();

                foreach (var cur in current)
                    children.AddRange(cur.GetChildren());

                if (children.Count > 0)
                {
                    for (int i = 0; i < children.Count - 1; i++)
                        children[i].Neighbor = children[i + 1];
                }

                current = children;
            }
        }

- saravananb35 December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the problem of this solution is that you do too many assumptions.
For example, consider the situation when you are given a third-party lib which contains class Node. And you get to know that method GetChildren() every time returns child nodes in random order. In this case your solution will not work.
Another assumption is that foreach iterator returns elements of collection in desired order. In general this is not true, it depends on the collection's container. Consider the situation when you are to use a container with random elements order. The solution again will not work.
In general the problem is dependency upon the assumptions.

- zr.roman December 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

While inserting node maintain horizontal and vertical level of each node as below ::

class node {
private :
    int data;
    node *left;
    node *right;
    int level[2];
public :
    node(node *rig,node *lef, int d, int vlevel,int hlevel)
    {
        data=d;
        left=lef;
        right=rig;
        level[0]=vlevel;
        level[1]=hlevel;
    }
    int getData()
    {
        return data;
    }
    node *getLeftChild(){
        return left;
    }
    node *getRightChild() {
        return right;
    }
    void setLeftChild(node *n){
        left=n;
    }
    void setRightChild(node *n) {
        right=n;
    }
    void sethLevel(int a)
    {
        level[1]=a;
    }
    int gethLevel()
    {
        return level[1];
    }
    void setvLevel(int a)
    {
        level[0]=a;
    }
    int getvLevel()
    {
        return level[0];
    }
    node *getNeighbor()
    {
        return neighbor;
    }
    void setNeighbor(node *n)
    {
        neighbor=n;
    }
};

class BST {
private :
    node *root;
    int _size;
    map<int,int> lev;
    vector<vector<int> > vec;
    int height;
public :
    BST() : root(NULL),height(0) {}
    BST(int *arr, int siz)
    {
        _size=siz;
        for(int i=0;i<_size;i++)
        {
            InsertNode(arr[i]);
        }
    }

    void InsertNode(int value)
    {
        int heit=0;
        node *temp=root;
        if(temp==NULL)
        {
            cout << "Adding the root Node" << value << endl;
            node *nod=new node(NULL,NULL,value,0,0);
            root=nod;

        }
        while(temp!=NULL)
        {
            heit++;
            if(value>temp->getData())
            {
                if(temp->getRightChild()==NULL)
                {
                    cout << "Adding the new node" << value << endl;
                    node *nod=new node(NULL,NULL,value,temp->getvLevel()+1,2*temp->gethLevel()+1);
                    temp->setRightChild(nod);
                    temp=NULL;
                }
                else
                {
                    cout << "Moving Right " << temp->getData() << endl;
                    temp=temp->getRightChild();
                }
            }
            else
            {
                if(temp->getLeftChild()==NULL)
                {
                    cout << "Adding the new node" << value << endl;
                    node *nod=new node(NULL,NULL,value,temp->getvLevel()+1,2*temp->gethLevel());
                    temp->setLeftChild(nod);
                    temp=NULL;
                }
                else
                {
                    cout << "Moving Left " << temp->getData() << endl;
                    temp=temp->getLeftChild();
                }
            }
        }
        if(heit>height)
            height=heit;
    }

Now maintain a map as below ::
map<pair<int,int>,node *>

Now given a node, you can get vertical level and horizontal level.
from that you get the neighbor by incrementing the horizontal level and fetching the node from the map. All the non values are set to NULL.

- raghu.aok December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void connectNeighbor(TreeNode root){

        if(root == null) return;

        TreeNode lastHead = root;//prevous level's head 
        TreeNode lastCurrent = null;//pointer
        TreeNode currentHead = null;//current level's head 
        TreeNode current = null;//pointer


        while (lastHead != null){

            lastCurrent = lastHead;

            while (lastCurrent !=null){

                if(lastCurrent.left != null){
                    if(currentHead == null)

                    currentHead = lastCurrent.left;
                    current = lastCurrent.left;
                }else {

                    current.next = lastCurrent.left;
                    current = current.next;
                }

                if(lastCurrent.right != null){

                    if(currentHead == null){

                        currentHead = lastCurrent.right;
                        current = lastCurrent.right;
                    }else {

                        current.next = lastCurrent.right;
                        current = current.next;
                    }
                }
                lastCurrent = lastCurrent.next;

            }

            lastHead = currentHead;
            currentHead = null;
        }

}

- abhay0609 December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

output will be :

A->NULL
B->C->NULL
D->E->NULL

- abhay0609 December 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c#.
DFS.
Direction: right to left.

public class Node<T> {

    public Node<T> LeftChild;
    public Node<T> RightChild;
    public T Data;
    public Node<T> Neighbor;

    public static void SetNeighbors( Node<T> root ) {
        _dic = new Dictionary<int, Node<T>>();
        _currLevel = -1;
        _setNeighbors( root );
    }

    static private void _setNeighbors( Node<T> node ) {

        _currLevel++;

        if ( _dic.ContainsKey( _currLevel ) ) {
            node.Neighbor = _dic[ _currLevel ];
        }

        if ( node.RightChild != null ) {
            _setNeighbors( node.RightChild );
        }
        if ( node.LeftChild != null ) {
            _setNeighbors( node.LeftChild );
        }

        _dic[ _currLevel ] = node;

        _currLevel--;
    }

    static private Dictionary<int, Node<T>> _dic;
    static private int _currLevel;
}

- zr.roman December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void connect(TreeLinkNode* root){

	queue<TreeLinkNode*> q;
	int count = 0;
	
	if(root != NULL) {
		q.push(root);
		count = 1;
	}
	
	while(count != 0){
	
		int newcount = 0;
		
		bool isFirstNode = true;
		TreeLinkNode* prev = NULL;
		
		for(int i = 0; i < count; ++i){
		
			TreeLinkNode* curr = q.front();
			q.pop();
			
			if(isFirstNode){
				isFirstNode = false;
				prev = curr;				
			}
			else{
				prev->next = curr;
				prev = curr;
			}			
			
			if(curr->left != NULL){
				q.push(curr->left);
				newcount++;
			}
			
			if(curr->right != NULL){
				q.push(curr->right);
				newcount++;
			}		
		}
		
		count = newcount;	
	}
}

- PoWerOnOff December 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
class Node{
	int data;
	Node left;
	Node right;
	Node friend;
	public Node(int data){
		this.data = data;
		this.left = null;
		this.right = null;
		this.friend = null;
	}
	public String toString(){
		if(friend != null)
		return " " + data + " : "+friend.data;
		else
			return " "+data+ " : NULL";
	}
}

public class FriendFinder{
	
	public static void printFriends(Node root){
		if(root == null)
		 {
		 	System.out.println("empty");
		 	return;
		 }
		else{
		Queue<Node> q1 = new LinkedList<Node>();	
		Queue<Node> q2 = new LinkedList<Node>();	
		q1.add(root);
		while(!q1.isEmpty() || !q2.isEmpty()){
			while(!q1.isEmpty())
				{
					if(q1.peek().left != null)
						q2.add(q1.peek().left);
					if(q1.peek().right != null)
						q2.add(q1.peek().right);
					Node pickedNode = q1.poll();
					pickedNode.friend = q1.peek();
					System.out.println(pickedNode);
				}
			while(!q2.isEmpty()){
					if(q2.peek().left != null)
						q1.add(q2.peek().left);
					if(q2.peek().right != null)
						q1.add(q2.peek().right);
					Node pickedNode = q2.poll(); 
					pickedNode.friend = q2.peek();
					System.out.println(pickedNode);
				}
			}
		}	
	}
	public static void main(String []args){
		Node root = new Node (1);
		Node n2 = new Node (2);
		Node n3 = new Node (3);
		Node n4 = new Node (4);
		Node n5 = new Node (5);
		Node n6 = new Node (6);
		root.left = n2; root.right = n3;
		n2.left = n4; 
		n3.left = n5;
		n3.right = n6;
		/*
			1
		   2   3
		  4   5  6
		*/
		printFriends(root);
		
	}

}

- maitra.partha December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1 : NULL
2 : 3
3 : NULL
4 : 5
5 : 6
6 : NULL

- maitra.partha December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to use BFS and if we use DFS, it would make it
more complicated and inefficient. We just need use a stack or array to store all children of nodes and assign the neighbor while traversing all nodes using BFS.

- Avinash Setty December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

DFS works greatly here,
we don't need to store all the children of nodes, we just need some container to store the last visited element at each level (because we move right to left). So, the space will be O(log n).
I provide the solution here.

- zr.roman December 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LinkNeighborNode {

	public static void main(String[] args) {
		Node root, nextLevel;
		while(true){
			nextLevel = linkLevel(root);
			if(nextLevel == null)
				break;
		}
	}

	private static Node linkLevel(Node firstParent){
		Node node = getFirstNode(firstParent);
		Node firstNode = null;
		
		if(node.left != null && node.right != null){
			node.left.neighbor = node.right;
			firstNode = node.right;
		} else {
			if(node.left != null) {
				firstNode = node.left;
			} else {
				firstNode = node.right;
			}
		}

		Node nextParentNode = node.neighbor;

		Node nodeToStart = firstNode;
		while(true){
			if(nextParentNode == null) {
				break;
			}
			if(nextParentNode.left != null && nextParentNode.right != null){
				nodeToStart.neighbor = nextParentNode.left;
				nextParentNode.left = nextParentNode.right;
				nodeToStart = nextParentNode.right;
				nextParentNode = nextParentNode.neighbor;
			} else {
				if(nextParentNode.left != null) {
					nodeToStart.neighbor = nextParentNode.left;
					nodeToStart = nextParentNode.left;
					nextParentNode = nextParentNode.neighbor;
				} else {
					nodeToStart.neighbor = nextParentNode.right;
					nodeToStart = nextParentNode.right;
					nextParentNode = nextParentNode.neighbor;
				}
			}
		}
		return firstNode;
	}

	private static Node getFirstNode(Node firstParent) {
		Node node = firstParent;
		while(true){
			if(node == null) {
				return null;
			}
			if(node.left == null && node.right == null){
				node = node.neighbor;
			} else {
				return node;
			}
		}
	}

	class Node {
		int val;
		Node left;
		Node right;
		Node neighbor;
	}
}

}

- naveen December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LinkNeighborNode {

	public static void main(String[] args) {
		Node root, nextLevel;
		while(true){
			nextLevel = linkLevel(root);
			if(nextLevel == null)
				break;
		}
	}

	private static Node linkLevel(Node firstParent){
		Node node = getFirstNode(firstParent);
		Node firstNode = null;
		
		if(node.left != null && node.right != null){
			node.left.neighbor = node.right;
			firstNode = node.right;
		} else {
			if(node.left != null) {
				firstNode = node.left;
			} else {
				firstNode = node.right;
			}
		}

		Node nextParentNode = node.neighbor;

		Node nodeToStart = firstNode;
		while(true){
			if(nextParentNode == null) {
				break;
			}
			if(nextParentNode.left != null && nextParentNode.right != null){
				nodeToStart.neighbor = nextParentNode.left;
				nextParentNode.left = nextParentNode.right;
				nodeToStart = nextParentNode.right;
				nextParentNode = nextParentNode.neighbor;
			} else {
				if(nextParentNode.left != null) {
					nodeToStart.neighbor = nextParentNode.left;
					nodeToStart = nextParentNode.left;
					nextParentNode = nextParentNode.neighbor;
				} else {
					nodeToStart.neighbor = nextParentNode.right;
					nodeToStart = nextParentNode.right;
					nextParentNode = nextParentNode.neighbor;
				}
			}
		}
		return firstNode;
	}

	private static Node getFirstNode(Node firstParent) {
		Node node = firstParent;
		while(true){
			if(node == null) {
				return null;
			}
			if(node.left == null && node.right == null){
				node = node.neighbor;
			} else {
				return node;
			}
		}
	}

	class Node {
		int val;
		Node left;
		Node right;
		Node neighbor;
	}
}

}

- naveen December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A variation of level-order traversal. Because something can only be a neighbor when it's on the same level, it means we should keep the current level and the next level separated. And because a Node only has knowledge of its immediate child, that means we really only need to know about two levels at any time. This algorithm runs in O(n) time, using O(n) space.

void attachNeighbors(Node root) {
	Queue<Node> currentLevel = new LinkedList<Node>();
	Queue<Node> nextLevel = new LinkedList<Node>();
	currentLevel.add(root);

	while (!currentLevel.isEmpty()) {
		final Node currentNode = currentLevel.remove();

		if (currentNode.left != null) {
			nextLevel.add(currentNode.left);
		}
		if (currentNode.right != null) {
			nextLevel.add(currentNode.right);
		}

		if (currentLevel.isEmpty()) {
			Queue<Node> temp = currentLevel; //so we don't use more memory than needed
			currentLevel = nextLevel;
			nextLevel = temp;
		} else {
			currentNode.neighbor = currentLevel.peek();
		}
	}
}

- Mdhornet90 December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This could be done using a level order traversal and collecting elements in same level. collection would be a map keyed on level and the value would be queue of elements. Rest is iterating over the map and assigning neighbors. Collect neighbors in a new map and then finally iterate over it. Below is a working code.

public class AssighnNeighbours {

	private static Map<Integer, Queue<Node>> map = new HashMap<>();
	private static Map<Integer, Integer> neighbours = new HashMap<>();

	public static void main(String[] args) {
		Node node = new Node(20);
		node.left = new Node(15);
		node.right = new Node(30);

		node.right.left = new Node(25);
		node.right.right = new Node(35);

		collectElementsOnSameLevel(node, 0);

		Set<Entry<Integer, Queue<Node>>> set = map.entrySet();

		for (Entry<Integer, Queue<Node>> entry : set) {

			Queue<Node> queue = entry.getValue();

			Node prev = queue.remove();

			if (queue.isEmpty()) {
				neighbours.put(prev.data, null);
			}

			while (!queue.isEmpty()) {

				Node next = queue.remove();
				neighbours.put(prev.data, next.data);

				prev = next;
			}
		}

		Set<Entry<Integer, Integer>> neighboursSet = neighbours.entrySet();

		for (Entry<Integer, Integer> entry : neighboursSet) {
			System.out.println("neighbour of : " + entry.getKey() + " is : " + entry.getValue());
		}

	}

	private static void collectElementsOnSameLevel(Node node, int level) {

		if (node != null) {
			if (map.get(level) != null) {
				Queue<Node> queue = map.get(level);
				queue.add(node);
			} else {
				Queue<Node> queue = new LinkedList<Node>();
				queue.add(node);
				map.put(level, queue);
			}

			collectElementsOnSameLevel(node.left, level + 1);
			collectElementsOnSameLevel(node.right, level + 1);
		}
	}
}

- Vishal Mehta December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void assignNeighborNode(Node root){
	Queue<Node> outerQue = new Queue<>();
	Queue<Node> innerQue = new Queue<>();
	outerQue.enqueue(root);
	
	while(!outerQue.isEmpty()){
		while(!outerQue.isEmpty())
			innerQue.enqueue(outerQue.dequeue());
			
		Node pre = null;
		while(!innerQue.isEmpty()){
			Node cur = innerQue.dequeue();
			if(pre != null){
				pre.neighbor = cur;
			}
			
			outerQue.enqueue(cur.left);
			outerQue.enqueue(cur.right);
			pre = cur;
		}
	}

}

- davie.lin76 December 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Searching neighbors by DFS

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication50
{
    class Program
    {
        static void Main(string[] args)
        {
            Node head = new Node();
            // input file contains, for example: 0 1 3 -1 -2 10
            string[] input_data = File.ReadAllText(@"g:\input.txt").Split(new char[] {' ','\r','\n','\t' });
            // create tree
            for (int i = 0; i < input_data.Length; i++)
            {
                int data = int.Parse(input_data[i]);
                if (i == 0) head.data = data; 
                else GrowTree(head, data);
            }
            // find neighbors for each node(if it is)
            ExploreNeighborhood(head);
        }
        static void ExploreNeighborhood(Node head)
        {
            Dictionary<int, Node> d = new Dictionary<int, Node>();
            if (head != null)
            {
                int level = 0;
                DFS(head, d ,ref level);
            }
        }
        // process tree by depth-first-search
        // from left to right
        // in each level remember last node without neighbor. 
        static Node DFS(Node node, Dictionary<int, Node> d ,ref int level)
        {
            level++;
            if (node.left != null)
            {
                if (d.ContainsKey(level))
                {
                    d[level].neighbor = node.left;
                    d[level] = node.left;
                }
                else
                {
                    d.Add(level, node.left);
                }
                DFS(node.left, d,ref level);
            }
            if(node.right !=null )
            {
                if (d.ContainsKey(level))
                {
                    d[level].neighbor = node.right;
                    d[level] = node.right;
                }
                else
                {
                    d.Add(level,node.right);
                }
                DFS(node.right, d,ref level);
            }
            level--;
            return node;
        }
        static void GrowTree(Node node, int data)
        {
            if (node != null)
            {
                if (node.data > data)
                {
                    if (node.left != null)
                    {
                        GrowTree(node.left, data);
                    }
                    else
                    {
                        node.left = new Node(data);
                    }
                }
                else {
                    if (node.right != null)
                    {
                        GrowTree(node.right, data);
                    }
                    else {
                        node.right = new Node(data);
                    }
                }
            }
        }
    }
    class Node
    {
        public int data;
        public Node left;
        public Node right;
        public Node neighbor;
        public Node()
        { }
        public Node(int in_data)
        {
            data = in_data;
        }
    }

}

- Trushnikov.Ivan December 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think using a BFS and maintaining lastNode of next level can help us set the neighbours. I am using Deque to peek the last node in the queue.

Below is solution in java.

public void setNeighbours() {
		if (root == null) {
			return;
		}
		TreeNode2 lastNode = root;
		Deque<TreeNode2> queue = new ArrayDeque<>();
		queue.add(root);
		while (!queue.isEmpty()) {

			TreeNode2 node = queue.remove();

			if (node.getlChild() != null) {
				queue.add(node.getlChild());
			} 
			if (node.rChild != null) {
				queue.add(node.getrChild());
			}

			if (lastNode == node) {
				node.setNeighbour(null);
				lastNode = queue.peekLast();
			} else {
				node.setNeighbour(queue.peekFirst());
			}
			System.out.println(node + " : " + node.getNeighbour());
		}
	}

- tarun.gupta.pec January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>

struct Node {
	Node* leftChild = nullptr;
	Node* rightChild = nullptr;
	char data;
	Node* neighbor = nullptr;
};

std::vector<Node*> nodeQueue;

void populateNeighbor(Node* root) {
	nodeQueue.push_back(root);

	while (nodeQueue.size() > 0) {
		int nodeCountAtDepth = nodeQueue.size();
		if (nodeCountAtDepth > 1) {
			for (int i = 1; i < nodeCountAtDepth; i++) {
				nodeQueue[i - 1]->neighbor = nodeQueue[i];
			}
		}

		for (int i = 0; i < nodeCountAtDepth; i++) {
			if (nodeQueue[0]->leftChild) { 
				nodeQueue.push_back(nodeQueue[0]->leftChild); 
			}

			if (nodeQueue[0]->rightChild) { 
				nodeQueue.push_back(nodeQueue[0]->rightChild); 
			}
			
                        // a slow operation -- O(n) -- could optimize
			nodeQueue.erase(nodeQueue.begin());
		}
	}
}

- rv January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{/*

Find the neighbors of a Tree
   A
  / \
  C  D
 /\  |\
 E F g h
 A:null
 C:D
*/
node{

    node leftChild;
    node rightChild;
    T data;
    node neighbhor;
    }
    
class Solution{

    public void getNeighbors(node n){
    
        if(n==null)
            return;
        node focusNode = n;
        n.neighbor=null;



        /*BFS*/
        node parent;
        Queue<node> q = new LinkedList<node>();
        List<node> visited = new ArrayList<node>();
        q.add(n);
        while(!q.isEmpty()){
            node focusNode = q.remove();
            
            visted.add(focusNode);
            
            
            parent = focusNode;
            
            
            
            if(focusNode.left!=null){
                focosNode = focusNode.left;
                focusNode.neighbor = parent.right;
            
                if(!visted.contains(parent.left)){
                    visted.add(parent.left);
                    q.add(parent.left);
                }
            }
            if(focusNode.right!=null){
                if(!visted.contains(parent.right)){
                    q.add(parent.right);
                    visted.add(parent.right);
                }
            }
	    else
			return;
            
        
        }
       
        


    }

}

- Omah February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hello?

- Omah February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node<T> {
	public T data;

	public Node<T> left;
	public Node<T> right;
	public Node<T> neighbour;
}

public class BinaryTreeTraversal<T> {
	private Node<T> root;
	private IVisitor<T> visitor;

	public BinaryTreeTraversal(Node<T> root) {
		this.root = root;
	}

	public void preOrder(IVisitor<T> v) {
		visitor = v;
		preOrder(root);
	}

	private void preOrder(Node<T> node) {
		if(node == null) return;
		visitor.visit(node);
		preOrder(node.left);
		preOrder(node.right);
	}
}

public class TestBinaryTreeTraversal extends TestCase {
	class IVisitorImpl implements IVisitor<String> {
		@Override
		public void visit(Node<String> node) {
			if (node == null)
				return;
			System.out.print(node.data);
			if (node.left != null) {
				node.left.neighbour = node.right;
			}
		}
	}

	class IVisitorNeighbourImpl implements IVisitor<String> {
		@Override
		public void visit(Node<String> node) {
			if (node == null)
				return;
			String data = (node.neighbour == null) ? null : node.neighbour.data;
			System.out.println(node.data + " --> " + data);
		}
	}

	public void testTraversal() {
		Node<String> root = defineDataNode();
		BinaryTreeTraversal<String> traversal = new BinaryTreeTraversal<>(root);
		traversal.preOrder(new IVisitorImpl());
		System.out.println("================================");
		traversal.preOrder(new IVisitorNeighbourImpl());
	}

	private Node defineDataNode() {
		Node<String> node = new Node<>();
		node.neighbour = null;
		node.data = "F";
		node.right = new Node<>();
		node.left = new Node<>();
		node.left.data = "B";
		node.right.data = "G";

		node.right.right = new Node<>();
		node.right.right.right = new Node<>();
		node.left.left = new Node<>();
		node.left.right = new Node<>();
		node.left.right.left = new Node<>();
		node.left.right.right = new Node<>();

		node.left.left.data = "A";
		node.left.right.data = "D";
		node.left.right.left.data = "C";
		node.left.right.right.data = "E";

		node.right.right.data = "I";
		node.right.right.left = new Node<>();
		node.right.right.left.data = "H";
		node.right.right.right.data="J";

		return node;
	}
}

- Pankaj Giri February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import datastructures.trees.IVisitor;
import datastructures.trees.Node;
import datastructures.trees.traversal.BinaryTreeTraversal;
import junit.framework.TestCase;

public class TestBinaryTreeTraversal extends TestCase {
class IVisitorImpl implements IVisitor<String> {
@Override
public void visit(Node<String> node) {
if (node == null)
return;
System.out.print(node.data);
if (node.left != null) {
node.left.neighbour = node.right;
}
}
}

class IVisitorNeighbourImpl implements IVisitor<String> {
@Override
public void visit(Node<String> node) {
if (node == null)
return;
String data = (node.neighbour == null) ? null : node.neighbour.data;
System.out.println(node.data + " --> " + data);
}
}

public void testTraversal() {
Node<String> root = defineDataNode();
BinaryTreeTraversal<String> traversal = new BinaryTreeTraversal<>(root);
traversal.preOrder(new IVisitorImpl());
System.out.println("================================");
traversal.preOrder(new IVisitorNeighbourImpl());
}

private Node defineDataNode() {
Node<String> node = new Node<>();
node.neighbour = null;
node.data = "F";
node.right = new Node<>();
node.left = new Node<>();
node.left.data = "B";
node.right.data = "G";

node.right.right = new Node<>();
node.right.right.right = new Node<>();
node.left.left = new Node<>();
node.left.right = new Node<>();
node.left.right.left = new Node<>();
node.left.right.right = new Node<>();

node.left.left.data = "A";
node.left.right.data = "D";
node.left.right.left.data = "C";
node.left.right.right.data = "E";

node.right.right.data = "I";
node.right.right.left = new Node<>();
node.right.right.left.data = "H";
node.right.right.right.data="J";

return node;
}
}


package datastructures.trees.traversal;

import datastructures.trees.IVisitor;
import datastructures.trees.Node;

public class BinaryTreeTraversal<T> {
private Node<T> root;
private IVisitor<T> visitor;

public BinaryTreeTraversal(Node<T> root) {
this.root = root;
}

public void preOrder(IVisitor<T> v) {
visitor = v;
preOrder(root);
}

private void preOrder(Node<T> node) {
if(node == null) return;
visitor.visit(node);
preOrder(node.left);
preOrder(node.right);
}
}

package datastructures.trees;

public class Node<T> {
public T data;

public Node<T> left;
public Node<T> right;
public Node<T> neighbour;
}

package datastructures.trees;

public interface IVisitor<T> {
public void visit(Node<T> node);
}

- Pankaj Giri February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if any issue with this please let us know

typedef struct _node{
	int data;
	_node *left;
	_node *right;
	_node *neighbore;
}node;
int height(node *root){
	if (root == NULL) return 0;
	return(1 + std::max(height(root->left), height(root->right)));
}
void levelOrder(node* root, int l, node** temp){
	if (root == NULL) return;
	if (l == 0){
		root->neighbore = *temp;
		*temp = root;
	}
	else{
		levelOrder(root->right, l - 1, temp);
		levelOrder(root->left, l - 1, temp);					
	}
}
void linkNeighbore(node* root){
	int h = height(root);
	root->neighbore = NULL;
	node* temp = NULL;
	for (int i = 1; i < h; i++)
		levelOrder(root, i, &temp);
}

- praveen pandit March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private void assignNeighbors(Node n){
      ArrayList<Node> current = new ArrayList<BinaryTree.Node>();
      if(n!=null) current.add(n);
      while(!current.isEmpty()){
          ArrayList<Node> parents = current;
          current = new ArrayList<BinaryTree.Node>();
          for(Node parent: parents){
              if(parent.left!=null && parent.right!=null){
                  parent.left.neighbor = parent.right;
              }
              if(parent.left!=null)current.add(parent.left);
              if(parent.right!=null) current.add(parent.right);
          }
      }
  }

- bfs approach April 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this can be solved use BFS with a canary, i.e. nullptr, for each layer.
push nodes into queue, when the level ends (reaching an canary, e.g. nullptr), propagate the canary

- Sean Locke April 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isnt this a level Order traversal using two queues ?

- Sean Locke June 09, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More