Given a binary tree, where each node has a third reference which is not yet initialized, go through the tree and point the third reference to the rightmost tree node on the same level. If there are no other nodes to its right, point it to null.

Question

Anonymous · Accepted Answer

I did it with a breadth first enqueueing of the tree nodes, then finding the last node in the queue that was on the same depth level as the target node.

import java.util.ArrayList;

public class Main {
	static Node targetNode;

	public static void main(String[] args) {
		Node root = new Node("root");
		
		/* Build an arbitrary Binary Tree */
		fillTree(root);
		findRightMostNeighbor(root);
		String neighbor = targetNode.rightmost != null ? targetNode.rightmost.name : "NULL";
		System.out.println("Target Node " + targetNode.name + " has the right most neighbor: " + neighbor);
	}
	
	public static void findRightMostNeighbor(Node root) {
		ArrayList temp = new ArrayList();
		ArrayList queue = new ArrayList();
		
		root.level = 0;
		temp.add(root);
		Node curr;
		int index = 0;
		
		/* Breadth first traversal */
		while(!temp.isEmpty()) {
			curr = temp.remove(0);
			queue.add(curr);
			
			if(curr.left != null) {
				curr.left.level = curr.level + 1;
				curr.left.index = index++;
				temp.add(curr.left);
			}
			
			if(curr.right != null) {
				curr.right.level = curr.level + 1;
				curr.right.index = index++;
				temp.add(curr.right);
			}
		}
		
		for(Node n : queue) {
			if(n.index > targetNode.index && n.level == targetNode.level) {
				targetNode.rightmost = n;
			}
		}
	}
	
	public static void fillTree(Node root) {
		Node one = new Node("1");
		Node two = new Node("2");
		root.left = one;
		root.right = two;
		
		Node three = new Node("3");
		Node four = new Node("4");
		one.left = three;
		one.right = four;
		
		Node five = new Node("5");
		Node six = new Node("6");
		two.left = five;
		two.right = six;
		
		/* Assign the target node */
		targetNode = three;
	}

}

class Node {
	public String name;
	public int level;
	public int index = 0;
	public Node left;
	public Node right;
	public Node rightmost;
	
	public Node(String name) {
		this.name = name;
	}
}

Anonymous · Answer

//BFS traversing and marking each Third Red with the last element in the queue for each level

import java.util.LinkedList;

public static void markRightMost(node root){

    if(root = null)
        return;
        
    //Acting as a Queue    
    LinkedList queue = new LinkedList();
    
    queue.add(root);
    
    //The main root has no rightmost node
    root.thirdRef = null;
    
    while(queue.size() > 0){
        
        LinkedList parents = queue;
        
        //getting new queue for new level
        queue = new LinkedList();
        
        for(node n: parents){
            
            if(n.left != null){
                queue.add(n.left);
            }
            
            if(n.right != null){
                queue.add(n.right);
            }
        }
        
        node last = queue.getLast()
        last.thirdRef = null;
        
        //remove last node
        queue.pop();
        
        //Filling in Third Reference
        for(node ele: queue){
            ele.thirdRef = last;
        }
    }
}

Microsoft

Microsoft Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches