Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
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;
}
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
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>();
elements.add(root.value);
map.put(level, elements);
}else{
elements.add(root.value);
}
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
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)
#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
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;
}
}
public static void printFirstAndLastPerLevel(Node head){
if (head == null){
System.out.println("handle any exception or error");
return;
}
System.out.println(head.data);
LinkedList <Node>level = new LinkedList <Node>();
addChildsToList(head, level);
LinkedList <Node>newLevel = new LinkedList <Node>();
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){
addChildsToList(currentNode, newLevel);
}
level = (LinkedList<Node>) newLevel.clone();
newLevel.clear();
}
}
private static void addChildsToList(Node elementToAdd , LinkedList <Node> listForElement){
if(elementToAdd.left != null){
listForElement.add(elementToAdd.left);
}
if(elementToAdd.right != null){
listForElement.add(elementToAdd.right);
}
}
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;
}
}
public static void printFirstAndLastPerLevel(Node head){
if (head == null){
System.out.println("handle any exception or error");
return;
}
System.out.println(head.data);
LinkedList <Node>level = new LinkedList <Node>();
addChildsToList(head, level);
LinkedList <Node>newLevel = new LinkedList <Node>();
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){
addChildsToList(currentNode, newLevel);
}
level = (LinkedList<Node>) newLevel.clone();
newLevel.clear();
}
}
private static void addChildsToList(Node elementToAdd , LinkedList <Node> listForElement){
if(elementToAdd.left != null){
listForElement.add(elementToAdd.left);
}
if(elementToAdd.right != null){
listForElement.add(elementToAdd.right);
}
}
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;
}
}
public static void printFirstAndLastPerLevel(Node head){
if (head == null){
System.out.println("handle any exception or error");
return;
}
System.out.println(head.data);
LinkedList <Node>level = new LinkedList <Node>();
addChildsToList(head, level);
LinkedList <Node>newLevel = new LinkedList <Node>();
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){
addChildsToList(currentNode, newLevel);
}
level = (LinkedList<Node>) newLevel.clone();
newLevel.clear();
}
}
private static void addChildsToList(Node elementToAdd , LinkedList <Node> listForElement){
if(elementToAdd.left != null){
listForElement.add(elementToAdd.left);
}
if(elementToAdd.right != null){
listForElement.add(elementToAdd.right);
}
}
#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);
}
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;
}
}
}
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;
}
}
}
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);
}());
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);
}());
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." ";
}
?>}}
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);
}
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;
}
}
}
}
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.AddLeft("2");
firstLastLevelTree.AddRight("3");
firstLastLevelTree.GotoLeftChild();
firstLastLevelTree.AddRight("4");
firstLastLevelTree.GotoRoot();
firstLastLevelTree.GotoRightChild();
firstLastLevelTree.AddLeft("5");
firstLastLevelTree.AddRight("6");
firstLastLevelTree.GotoLeftChild();
firstLastLevelTree.AddLeft("7");
firstLastLevelTree.GotoLeftChild();
firstLastLevelTree.AddRight("8");
doBFS(firstLastLevelTree);
Console.ReadLine();
}
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;
}
public void AddRight(T val)
{
_currentNode.Right = new TreeNode<T>(val);
_currentNode.Right.Parent = _currentNode;
}
public void AddLeft(T val)
{
_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;
}
}
}
#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;
}
...
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() {
ArrayList<LinkedList> nodesPerLevel = new ArrayList<>();
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) {
records.add(hd, new LinkedList());
}
records.get(hd).addNode(root.value);
getNodesForLevel(records, root.left, hd + 1);
getNodesForLevel(records, root.right, hd + 1);
}
1
2 3
4 6
7
8
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>();
list.Add(root);
while(list.Count > 0)
{
result.Add(list[0].Value);
if (list.Count > 1)
result.Add(list[list.Count - 1].Value);
var next = new List<TreeNode>();
foreach(var node in list)
{
if (node.Left != null)
next.Add(node.Left);
if (node.Right != null)
next.Add(node.Right);
}
list = next;
}
return result;
}
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);
}
}
}
#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;
}
Use Breadth first search technique.
- Visu September 21, 2015Put all the elements in a queue and push an empty node into queue after the last node at each level.