## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

Put all the elements in a queue and push an empty node into queue after the last node at each level.

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

Good idea! I implemented your idea in C++.

vector<int> firstLastNodes(TreeNode *root){

queue<TreeNode*> q;
vector<int> res;
int count = 0;

if(root != NULL) {
count = 1;
q.push(root);
}

while(count != 0){

int newcount = 0;
vector<int> level;

for(int i = 0; i < count; i++){

TreeNode *node = q.front();
q.pop();

level.push_back(node->val);

if(node->left != NULL){
newcount++;
q.push(node->left);
}

if(node->right != NULL){
newcount++;
q.push(node->right);
}
}

res.push_back(level.back()->val);	// left node

if(level.size() >= 2){
res.push_back(level.front()->val);		// right node
}

count = newcount;
}

return res;
}

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

import java.util.Map;
import java.util.HashMap;

public class Node<T> {

private T data;
private Node<T> left;
private Node<T> right;

public void printFirstLastOnEachLevel() {
Map<Integer, Node<T>> firstNodes = new HashMap<>();
Map<Integer, Node<T>> lastNodes = new HashMap<>();
int maxLeft = populate(this.left, firstNodes, lastNodes, 1);
int maxRight = populate(this.right, firstNodes, lastNodes, 1);

System.out.println(data);
int max = Math.max(maxLeft, maxRight);
for (int depth = 1; depth <= max; ++depth) {
Node<T> first = firstNodes.get(depth);
Node<T> last = lastNodes.get(depth);
if (first != null) {
System.out.print(" " + first.data);
}
if (last != null) {
System.out.print(" " + last.data);
}
}
}

private int populate(Node<T> node, Map<Integer, Node<T>> firstNodes, Map<Integer, Node<T>> lastNodes, int depth) {
if (node == null) {
return depth - 1;
} else {
if (firstNodes.get(depth) == null) {
firstNodes.put(depth, node);
} else {
lastNodes.put(depth, node);
}

int maxLeft = populate(node.left, firstNodes, lastNodes, depth + 1);
int maxRight = populate(node.right, firstNodes, lastNodes, depth + 1);
return Math.max(maxLeft, maxRight);
}
}

}

O(N) time, O(logN) space

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

import java.util.*;

public class FirstAndLastNodeLevelTree<T>{

private Node<T> root;

private static class Node<T>{
T value;
Node left;
Node right;

Node(){}
Node(T value){
this.value = value;
}
Node(T value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}

public String toString(){
return this.value + "";
}
}

//S(n) = O(n)
Map<Integer, ArrayList<T>> map = new LinkedHashMap<Integer, ArrayList<T>>();

//T(n) = O(n)
public void printFirstAndLastNode(Node<T> root){
this.printFirstAndLastNodeUtil(1, root);
for(Integer level : map.keySet()){
ArrayList<T> elements = map.get(level);
if(elements.size() == 1){
System.out.println("root:" + elements.get(0));
}else{
System.out.println("Level:" +  level + " First: " + elements.get(0) + " Last:" + elements.get(elements.size() - 1));
}
}
}

private void printFirstAndLastNodeUtil(Integer level, Node<T> root){
if(root == null){
return;
}
ArrayList<T> elements = map.get(level);
if(elements == null){
elements = new ArrayList<T>();
map.put(level, elements);
}else{
}
printFirstAndLastNodeUtil(level + 1, root.left);
printFirstAndLastNodeUtil(level + 1, root.right);
}

public static void main(String[] args) {
Node<Integer> rootNode = new Node<Integer>(50);

rootNode.left = new Node(30);
rootNode.right = new Node(90);

rootNode.left.left = new Node(20);
rootNode.left.right = new Node(40);
rootNode.right.left = new Node(85);
rootNode.right.right = new Node(100);

FirstAndLastNodeLevelTree<Integer> f = new FirstAndLastNodeLevelTree<Integer>();
f.printFirstAndLastNode(rootNode);
}
}

Output:
java FirstAndLastNodeLevelTree
root:50
Level:2 First: 30 Last:90
Level:3 First: 20 Last:100

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

Any ideas to reduce the space complexity would be appreciated !

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

A simple optimization is keeping a max of 2 elements in each array list, which would reduce space complexity from O(n) (elements in tree) to O(k) (height of tree)

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

not to put everything in the list just first and new entry override the second one

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

#include <iostream>
#include <memory>
#include <queue>

struct Node
{
typedef std::shared_ptr<Node> Ptr;

int m_value;
int m_label;
std::shared_ptr<Node> m_left;
std::shared_ptr<Node> m_right;

Node(int value)
: m_value(value)
{
}
};

Node::Ptr createTree()
{
Node::Ptr root(new Node(1));
root->m_left.reset(new Node(2));
root->m_right.reset(new Node(3));
root->m_left->m_right.reset(new Node(4));
root->m_right->m_right.reset(new Node(6));
root->m_right->m_left.reset(new Node(5));
root->m_right->m_left->m_left.reset(new Node(7));
root->m_right->m_left->m_left->m_right.reset(new Node(8));
return root;
}

void outputLeftAndRightNodesAtEachLevel(Node::Ptr root)
{
if (!root)
{
return;
}

std::queue<Node::Ptr> queue;
queue.push(root);

root->m_label = 1;
Node::Ptr prevNode;
bool oneNodeAtCurrentLevel = true;

do
{
Node::Ptr node = queue.front();
queue.pop();

if (!prevNode)
{
// Output the root.
std::cout << "Level " << node->m_label << ": Left-" << node->m_value;
oneNodeAtCurrentLevel = true;
}
else if (node->m_label != prevNode->m_label)
{
// Next level starting.
if (!oneNodeAtCurrentLevel)
{
// Output the rightmost node of the previous level.
std::cout << " Right-" << prevNode->m_value;
}

// Output the leftmost node of the new level.
std::cout << std::endl << "Level " << node->m_label << ": Left-" << node->m_value;
oneNodeAtCurrentLevel = true;
}
else
{
// More than one node at the current level.
oneNodeAtCurrentLevel = false;
}

if (node->m_left)
{
node->m_left->m_label = node->m_label + 1;
queue.push(node->m_left);
}

if (node->m_right)
{
node->m_right->m_label = node->m_label + 1;
queue.push(node->m_right);
}

prevNode = node;

} while (!queue.empty());

// Ensure that the right node of the last level is output.
if (!oneNodeAtCurrentLevel)
{
std::cout << " Right-" << prevNode->m_value;
}

std::cout << std::endl;
}

int main()
{
Node::Ptr root(new Node(1));
root->m_left.reset(new Node(2));
root->m_right.reset(new Node(3));
root->m_left->m_right.reset(new Node(4));
root->m_right->m_right.reset(new Node(6));
root->m_right->m_left.reset(new Node(5));
root->m_right->m_left->m_left.reset(new Node(7));
root->m_right->m_left->m_left->m_right.reset(new Node(8));

outputLeftAndRightNodesAtEachLevel(root);
return 0;
}

Output:
Level 1: Left-1
Level 2: Left-2 Right-3
Level 3: Left-4 Right-6
Level 4: Left-7
Level 5: Left-8

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

My solution: complexity as peekLast and peekFirst are O(1) the final solution would be O(N).
Memory 2N as I create a copy of each level.

public class Node {
int data = 0;
Node left;
Node right;

Node (int data){
this.data = data;
}

}

System.out.println("handle any exception or error");
return;
}

while (!level.isEmpty()){
System.out.print("First of level " + (level.peekFirst()).data+ "  ") ;
System.out.println("Last of level " + (level.peekLast()).data);

for(Node currentNode : level){
}

newLevel.clear();
}

}

}

}
}

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

My solution:
Complexity: O(N) because peekFirst and peekLast are both O(1)
Memory: 2N as make two copies of each level

public class Node {
int data = 0;
Node left;
Node right;

Node (int data){
this.data = data;
}

}

System.out.println("handle any exception or error");
return;
}

while (!level.isEmpty()){
System.out.print("First of level " + (level.peekFirst()).data+ "  ") ;
System.out.println("Last of level " + (level.peekLast()).data);

for(Node currentNode : level){
}

newLevel.clear();
}

}

}

}
}

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

My solution,
Complexity: O(N) as peekFirst and peekLast are both O(1)
Memory: 2(N) as I make a copy of each level

public class Node {
int data = 0;
Node left;
Node right;

Node (int data){
this.data = data;
}

}

System.out.println("handle any exception or error");
return;
}

while (!level.isEmpty()){
System.out.print("First of level " + (level.peekFirst()).data+ "  ") ;
System.out.println("Last of level " + (level.peekLast()).data);

for(Node currentNode : level){
}

newLevel.clear();
}

}

}

}
}

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

#include <iostream>
#include <vector>

using namespace std;

struct Node {
int data;
Node* left, *right;
};

void findFirstnLastOfLevel(Node* root, vector<pair<unsigned int, unsigned int>>& result, unsigned int level ) {

if (result[level].first == -1)//left for this level not yet found
result[level].first = root->data;
else
result[level].second = root->data;//always overwrite the rightest node

if (root->left != NULL)
findFirstnLastOfLevel(root->left, result, level+1);
if (root->right != NULL)
findFirstnLastOfLevel(root->right, result, level+1);

}

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

printFirstLast(Node * node)
{
Queue<Node*> queue;
Queue<Node*> queue2;

bool printItem = true;

queue.enqueue(node);
printItem =  true;

while( ! queue.IsEmpty() ){

if (queue.Count() == 1)
printItem = true;

Node *tmp = queue.dequeue();

if (printItem ){
Print(tmp);
printItem = true;
}

if ( tmp->left != null)
queue2.enqueue(tmp->left);

if ( tmp->right != null)
queue2.enqueue(tmp->right);

if(queue.IsEmpty){
while( !queue2.IsEmpty())
queue.enqueue( queue2.dequeue() );

printItem = true;
}
}
}

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

class Node {

private:
Node* _left;
Node* _right;

public:
T _val;

Node();
Node(const T& val);
void insert(const T& val);
void printFirstAndLastNodesPerLevel();
};

template <typename T>
void Node<T>::printFirstAndLastNodesPerLevel() {

queue<Node<T>> Q;
Q.push(*this);

int currCount = 1;
int levelSize = 1;
int nextCount = 0;

while (Q.size() > 0) {

Node<T> curr = Q.front();
Q.pop();

--currCount;

if (currCount == levelSize - 1 || currCount == 0) {
cout << curr._val << " ";
}
if (curr._left) {
Q.push(*(curr._left));
++nextCount;
}
if (curr._right) {
Q.push(*(curr._right));
++nextCount;
}
if (currCount == 0) {
currCount = nextCount;
levelSize = nextCount;
nextCount = 0;
}
}
}

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

With Javascript :)
I think its O(n) time and O(1) space

(function() {

// Print first and last node of all the levels of a tree.
// Ex if tree is -
//
// root->data = 1
// root->left->data = 2
// root->right->data = 3
// root->left->right->data = 4
// root->right->right->data = 6
// root->right->left->data = 5
// root->right->left->left->data = 7
// root->right->left->left->right->data = 8
//
// Output - 1 2 3 4 6 7 8

function Node(data, left, right) {
this.data = data;
this.left = left || null;
this.right = right || null;
}

// Creating our test case, in reverse
var n8 = new Node(8);
var n7 = new Node(7, null, n8);
var n5 = new Node(5, n7, null);
var n6 = new Node(6);
var n4 = new Node(4);
var n3 = new Node(3, n5, n6);
var n2 = new Node(2, n4);
var n1 = new Node(1, n2, n3);

// Create a queue for our nodes
var queue = [], output = "";
var currlevel = n1.level = 1;
var prevnode = null;
// Keep track of the levels, for edges
var levelsize = 1;
queue.push(n1);

while(queue.length !== 0) {
var node = queue.shift();
if (node.level === 1 || node.level !== currlevel) {
output += node.data + ' ';
currlevel = node.level;
levelsize = 1;
}
if (node.left !== null) {
node.left.level = node.level + 1;
queue.push(node.left);
}
if (node.right !== null) {
node.right.level = node.level + 1;
queue.push(node.right);
}
if (queue[0] !== undefined && queue[0].level !== currlevel && levelsize > 1) {
output += node.data + ' ';
}
levelsize++;
}

console.log(output);

}());

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

With javascript
(I think) O(n) time and O(n) space

(function() {

// Print first and last node of all the levels of a tree.
// Ex if tree is -
//
// root->data = 1
// root->left->data = 2
// root->right->data = 3
// root->left->right->data = 4
// root->right->right->data = 6
// root->right->left->data = 5
// root->right->left->left->data = 7
// root->right->left->left->right->data = 8
//
// Output - 1 2 3 4 6 7 8

function Node(data, left, right) {
this.data = data;
this.left = left || null;
this.right = right || null;
}

// Creating our test case, in reverse
var n8 = new Node(8);
var n7 = new Node(7, null, n8);
var n5 = new Node(5, n7, null);
var n6 = new Node(6);
var n4 = new Node(4);
var n3 = new Node(3, n5, n6);
var n2 = new Node(2, n4);
var n1 = new Node(1, n2, n3);

// Create a queue for our nodes
var queue = [], output = "";
var currlevel = n1.level = 1;
var prevnode = null;
// Keep track of the levels, for edges
var levelsize = 1;
queue.push(n1);

while(queue.length !== 0) {
var node = queue.shift();
if (node.level === 1 || node.level !== currlevel) {
output += node.data + ' ';
currlevel = node.level;
levelsize = 1;
}
if (node.left !== null) {
node.left.level = node.level + 1;
queue.push(node.left);
}
if (node.right !== null) {
node.right.level = node.level + 1;
queue.push(node.right);
}
if (queue[0] !== undefined && queue[0].level !== currlevel && levelsize > 1) {
output += node.data + ' ';
}
levelsize++;
}

console.log(output);

}());

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

BFS:

{{
<?php

class NNode {
public \$data;
public \$right;
public \$left;

public function __construct(){
\$right = null;
\$left = null;
}

}

\$root = new NNode();
\$root->data = 1;

\$root->left = new NNode();
\$root->left->data = 2;

\$root->right = new NNode();
\$root->right->data = 3;

\$root->left->right = new NNode();
\$root->left->right->data = 4;

\$root->right->left = new NNode();
\$root->right->left->data = 5;

\$root->right->right= new NNode();
\$root->right->right->data = 6;

\$root->right->left->left = new NNode();
\$root->right->left->left->data = 7;

\$root->right->left->left->right = new NNode();
\$root->right->left->left->right->data = 8;

\$q = array();
\$q[] = \$root;

while(count(\$q)>0){
\$n = array_shift(\$q);

if (\$n->left!=null){
array_push(\$q, \$n->left);
}
if (\$n->right!=null){
array_push(\$q, \$n->right);
}
echo \$n->data." ";
}

?>}}

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

See here: cpluspluslearning-petert.blogspot.co.uk/2015/09/bts-print-first-and-last-nodes-of-each.html

Test

void TestCasesOfFirstAndLastOfEachLevelOfTree()
{
std::vector<int> testInput{ 1 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);

std::vector<TreeNode<int>*> result;
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 1);
assert(*result[0]->data == 1);
DeleteTree(&rootBFS);

testInput = { 1, 2 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 2);
assert(*result[0]->data == 2);
assert(*result[1]->data == 1);
DeleteTree(&rootBFS);

testInput = { 1, 2, 3 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 3);
assert(*result[0]->data == 2);
assert(*result[1]->data == 1);
assert(*result[2]->data == 3);
DeleteTree(&rootBFS);

testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetFirstAndLastOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 7);
// Tree:
// 6
// 3, 8
// 1, 4, 7, 9
// 2, 5, 10
assert(*result[0]->data == 6);
assert(*result[1]->data == 3);
assert(*result[2]->data == 8);
assert(*result[3]->data == 1);
assert(*result[4]->data == 9);
assert(*result[5]->data == 2);
assert(*result[6]->data == 10);
DeleteTree(&rootBFS);

}

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

Complexity = O(n)
Space = The width of the tree

void BST::printOrillas(nodet* r){
if(r != NULL){
bool tof = true;
int contPrevio = 1;
int contActual = 0;
nodet *aux;
queue<nodet *> fila;
fila.push(r);

while(!fila.empty()){

aux = fila.front();
fila.pop();

if(aux->getLeft() != NULL){
fila.push(aux->getLeft());
contActual++;
}

if(aux->getRight() != NULL){
fila.push(aux->getRight());
contActual++;
}

if(contPrevio-- == 1 || tof){
cout<< aux->getData()<<" ";
tof = false;
}

if(contPrevio == 0){
contPrevio = contActual;
contActual = 0;
tof = true;
}
}
}
}

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

can be done with bfs,right?

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

plain old C# solution with a queue and BFS for a Generic Binary Tree

class PrintFirstAndLastNodeEveryLevel
{
static void Main(string[] args)
{
//Create the tree in question
BinaryTree<string> firstLastLevelTree = new BinaryTree<string>("1");

firstLastLevelTree.GotoLeftChild();

firstLastLevelTree.GotoRoot();
firstLastLevelTree.GotoRightChild();

firstLastLevelTree.GotoLeftChild();

firstLastLevelTree.GotoLeftChild();

doBFS(firstLastLevelTree);
}

static void doBFS(BinaryTree<string> tree)
{
Queue<BinaryTree<string>.TreeNode<string>> sds = new Queue<BinaryTree<string>.TreeNode<string>>();
tree.GotoRoot();
sds.Enqueue(tree.GetCurrentNode());
while(sds.Count > 0)
{
Queue<BinaryTree<string>.TreeNode<string>> newQ = new Queue<BinaryTree<string>.TreeNode<string>>();
int counter = 0;
foreach (var node in sds)
{
if (counter == 0 || (counter == sds.Count - 1))
Console.WriteLine(node.Value);
if (node.HasLeft())
newQ.Enqueue(node.Left);
if (node.HasRight())
newQ.Enqueue(node.Right);
counter++;
}
sds = newQ;
}
}

BinaryTree.cs
namespace Libraries
{
public class BinaryTree<T>
{
TreeNode<T> _root;
TreeNode<T> _currentNode;

public class TreeNode<T>
{
public TreeNode<T> Parent;
public TreeNode<T> Right;
public TreeNode<T> Left;
public T Value;
public TreeNode(T val)
{
Value = val;
}

public bool HasChildren()
{
return Left != null || Right != null;
}

public bool HasLeft()
{
return Left != null;
}

public bool HasRight()
{
return Right != null;
}
}

public BinaryTree(T val)
{
_root = new TreeNode<T>(val);
_root.Value = val;
_currentNode = _root;
}

{
_currentNode.Right = new TreeNode<T>(val);
_currentNode.Right.Parent = _currentNode;
}

{
_currentNode.Left = new TreeNode<T>(val);
_currentNode.Left.Parent = _currentNode;
}

public bool GotoLeftChild()
{
if(_currentNode.Left != null)
{
_currentNode = _currentNode.Left;
return true;
}
return false;
}

public bool GotoRightChild()
{
if (_currentNode.Right != null)
{
_currentNode = _currentNode.Right;
return true;
}
return false;
}

public bool GotoParent()
{
if(_currentNode.Parent != null)
{
_currentNode = _currentNode.Parent;
return true;
}
return false;
}

public void GotoRoot()
{
_currentNode = _root;
}

public T GetCurrentValue()
{
return _currentNode.Value;
}

public TreeNode<T> GetCurrentNode()
{
return _currentNode;
}

public bool CurrentNodeHasChildren()
{
return _currentNode.Left != null || _currentNode.Right != null;
}

public bool CurrentNodeHasLeft()
{
return _currentNode.Left != null;
}
public bool CurrentNodeHasRight()
{
return _currentNode.Right != null;
}
}
}

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

#include <iostream>
#include <queue>

struct Node {
int value;
Node * leftNode;
Node * rightNode;
};

void printNodeAtTheSameLevel(Node * node) {
std::queue<Node *> nodeQueue;

if (node != nullptr) {
nodeQueue.push(node);
do {
std::cout << nodeQueue.front()->value << std::endl;
if (nodeQueue.front()->leftNode != nullptr) {
nodeQueue.push(nodeQueue.front()->leftNode);
}
if (nodeQueue.front()->rightNode != nullptr) {
nodeQueue.push(nodeQueue.front()->rightNode);
}
nodeQueue.pop();
} while (nodeQueue.empty() == false);
}
}

int main(int argc, const char * argv[]) {
Node * binaryTree;

binaryTree                                              = new Node{1, nullptr, nullptr};
binaryTree->leftNode                                    = new Node{2, nullptr, nullptr};
binaryTree->rightNode                                   = new Node{3, nullptr, nullptr};
binaryTree->leftNode->rightNode                         = new Node{4, nullptr, nullptr};
binaryTree->rightNode->leftNode                         = new Node{5, nullptr, nullptr};
binaryTree->rightNode->rightNode                        = new Node{6, nullptr, nullptr};
binaryTree->rightNode->leftNode->leftNode               = new Node{7, nullptr, nullptr};
binaryTree->rightNode->leftNode->leftNode->rightNode    = new Node{8, nullptr, nullptr};

printNodeAtTheSameLevel(binaryTree);

return 0;
}

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

...
root = new Node(1);
root.left = new Node(2);
root.right = 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.left.right = new Node(8);
...

public void printOutLeafsAtEachLevel() {

getNodesForLevel(nodesPerLevel, root, 0);

for (LinkedList list : nodesPerLevel) {

if(list.peek() == list.peekTail()) {
System.out.println(list.peek());
}
else
{
System.out.println(list.peek() + " " + list.peekTail()+" ");
}
}
}

public void getNodesForLevel(ArrayList<LinkedList> records, Node root, int hd) {
if (root == null) {
return;
}

if (hd >= records.size() || records.get(hd) == null) {
}

getNodesForLevel(records, root.left, hd + 1);
getNodesForLevel(records, root.right, hd + 1);
}

1
2 3
4 6
7
8

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

Breadth traversal, uses two list one to hold the nodes in the current level and another to add the nodes in the next level.

public List<int> GetFirstLastOnLevel(TreeNode root)
{
var result = new List<int>();
if (root == null)
return result;

var list = new List<TreeNode>();

while(list.Count > 0)
{
if (list.Count > 1)

var next = new List<TreeNode>();
foreach(var node in list)
{
if (node.Left != null)
if (node.Right != null)
}

list = next;
}

return result;
}

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

class bNode
{
enum SIDE { LEFT, RIGHT};
public bNode left;
public bNode right;
public int nodeId;
public bNode(int Id)
{
left = null;
right = null;
nodeId = Id;
}

class Btree
{
static void Main(string[] args)
{
bNode root = null;
SortedDictionary<int, Dictionary<SIDE,bNode>> nodeForTheLevel = new SortedDictionary<int, Dictionary<SIDE, bNode>>();
GetSideNodeForTheLevel(root, nodeForTheLevel, 0, SIDE.LEFT);
GetSideNodeForTheLevel(root, nodeForTheLevel, 0, SIDE.RIGHT);
foreach (int level in nodeForTheLevel.Keys)
{
Console.WriteLine("Level " + level + " leftmost node = " + nodeForTheLevel[level][SIDE.LEFT].nodeId + " rightmost node = " + nodeForTheLevel[level][SIDE.RIGHT].nodeId);
}

}

static void GetSideNodeForTheLevel(bNode currentNode, SortedDictionary<int, Dictionary<SIDE, bNode>> nodeForTheLevel, int level, SIDE side)
{
if (!nodeForTheLevel.ContainsKey(level))
{
nodeForTheLevel[level] = new Dictionary<SIDE, bNode>();
}

if (!nodeForTheLevel[level].ContainsKey(side))
{
nodeForTheLevel[level][side] = currentNode;
}
bNode firstNode = (side == SIDE.LEFT) ? currentNode.left : currentNode.right;
bNode lastNode = (side == SIDE.LEFT) ? currentNode.right : currentNode.left;
if (firstNode != null)
GetSideNodeForTheLevel(firstNode, nodeForTheLevel, level + 1, side);

if (lastNode != null)
GetSideNodeForTheLevel(lastNode, nodeForTheLevel, level + 1, side);
}
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <memory>
#include <queue>

struct Node
{
typedef std::shared_ptr<Node> Ptr;

int m_value;
int m_label;
std::shared_ptr<Node> m_left;
std::shared_ptr<Node> m_right;

Node(int value)
: m_value(value)
{
}
};

Node::Ptr createTree()
{
Node::Ptr root(new Node(1));
root->m_left.reset(new Node(2));
root->m_right.reset(new Node(3));
root->m_left->m_right.reset(new Node(4));
root->m_right->m_right.reset(new Node(6));
root->m_right->m_left.reset(new Node(5));
root->m_right->m_left->m_left.reset(new Node(7));
root->m_right->m_left->m_left->m_right.reset(new Node(8));
return root;
}

void outputLeftAndRightNodesAtEachLevel(Node::Ptr root)
{
if (!root)
{
return;
}

std::queue<Node::Ptr> queue;
queue.push(root);

root->m_label = 1;
Node::Ptr prevNode;
bool oneNodeAtCurrentLevel = true;

do
{
Node::Ptr node = queue.front();
queue.pop();

if (!prevNode)
{
// Output the root.
std::cout << "Level " << node->m_label << ": Left-" << node->m_value;
oneNodeAtCurrentLevel = true;
}
else if (node->m_label != prevNode->m_label)
{
// Next level starting.
if (!oneNodeAtCurrentLevel)
{
// Output the rightmost node of the previous level.
std::cout << " Right-" << prevNode->m_value;
}

// Output the leftmost node of the new level.
std::cout << std::endl << "Level " << node->m_label << ": Left-" << node->m_value;
oneNodeAtCurrentLevel = true;
}
else
{
// More than one node at the current level.
oneNodeAtCurrentLevel = false;
}

if (node->m_left)
{
node->m_left->m_label = node->m_label + 1;
queue.push(node->m_left);
}

if (node->m_right)
{
node->m_right->m_label = node->m_label + 1;
queue.push(node->m_right);
}

prevNode = node;

} while (!queue.empty());

// Ensure that the right node of the last level is output.
if (!oneNodeAtCurrentLevel)
{
std::cout << " Right-" << prevNode->m_value;
}

std::cout << std::endl;
}

int main()
{
Node::Ptr root(new Node(1));
root->m_left.reset(new Node(2));
root->m_right.reset(new Node(3));
root->m_left->m_right.reset(new Node(4));
root->m_right->m_right.reset(new Node(6));
root->m_right->m_left.reset(new Node(5));
root->m_right->m_left->m_left.reset(new Node(7));
root->m_right->m_left->m_left->m_right.reset(new Node(8));

outputLeftAndRightNodesAtEachLevel(root);
return 0;
}

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.

### 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.