Microsoft Interview Question SDE-2s
Country: United States
Interview Type: In-Person
Assuming that the total number of elements is N, we must avoid trying to go to the left because we will achieve O (N) running time. Instead, first i would find the root and in the same time i would count my depth level. Then i would try to traverse down by trying to peek on each step the most left node. This down traversal i would do until my depth is reached. Total running time would be O (log N)
But that is not O(log N) in worst or average case. It is O(log N) in the best case only, although I do agree DFS is better on average than BFS.
In worst case the tree is linear and your node can be the last.
In general, your tree can still be inbalanced and you may have to traversal n/2 or n/3 nodes to find the answer.
O (Log N) it's NOT the best case, it's the average case. The best case is O (1) if the tree is plat (all nodes has a single root, the root of the tree) and I have to perform only two steps to find out the left most node.
The worst case will be O(N) because you are not travelling only path. Suppose first time you chose the left node but the depth of the node is h-2 that means the if your input node is in height h then you should chose the right node first.The way you solve is using recursion. That will end up using O(N) in worst case.
public void lowestInLevel(Node current) {
int level = 0;
Node runner = current;
while(runner.parent != null) {
runner = runner.parent;
level++;
}
int i = 0;
while(count != i) {
if(runner.left != null)
runner = runner.left;
else
runner = runner.right;
i++;
}
System.out.println(runner);
}
public void lowestInLevel(Node current) {
int level = 0;
Node runner = current;
while(runner.parent != null) {
runner = runner.parent;
level++;
}
int i = 0;
while(count != i) {
if(runner.left == null && runner.right == null)
throw new NoSuchElementException();
else if(runner.left != null)
runner = runner.left;
else
runner = runner.right;
i++;
}
System.out.println(runner);
}
node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node * findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);
}
node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node* findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace ConsoleApplication45
{
class Program
{
static void Main(string[] args)
{
// data for creating tree
// This file contains a string of numbers separated by spaces
string[] input_data = File.ReadAllText(@"G:\input.txt").Split(new char[] { ' ','\n','\r','\t'}, StringSplitOptions.RemoveEmptyEntries);
if (input_data.Length == 0)
{
return;
}
Tree node = new Tree(); // creating of root
bool is_head = true;
// creating of tree
for (int i =0; i< input_data.Length; i++)
{
// this case is needed to fill the root
if (is_head)
{
node.data = int.Parse(input_data[i]);
is_head = false;
}
else
{
node = GrowingTree(node, int.Parse(input_data[i]));
}
}
// Now we have a tree for test
// Get node for test
int test_counter =2;
while (node != null && test_counter > 0)
{
node = node.right;
test_counter--;
}
node = GetLeftMost(node);
}
static Tree GetLeftMost(Tree item)
{
int level = 0;
if (item == null)
{
return null;
}
// Get root
while (item.parent !=null)
{
item = item.parent;
level++;
}
// Get left most
while (level > 0)
{
// Left sub tree is not null
if (item.left != null)
{
item = item.left;
level--;
}
// Get right sub tree
else {
item = item.right;
level--;
}
}
return item;
}
static Tree GrowingTree(Tree node, int data)
{
if (node.data > data)
{
if (node.left != null)
{
GrowingTree(node.left, data);
}
else
{
node.left = new Tree(node, data);
}
}
else
{
if (node.right != null)
{
GrowingTree(node.right, data);
}
else
{
node.right = new Tree(node, data);
}
}
return node;
}
}
class Tree
{
public Tree parent;
public Tree left;
public Tree right;
public int data;
// Constructors
public Tree()
{ }
public Tree(Tree in_parent, int in_data)
{
data = in_data;
parent = in_parent;
}
}
}
Worst case time complexity will be O(N) (for any type of a tree: complete binary tree (i.e. a heap), full binary tree, balanced or unbalanced tree, binary search tree, full binary tree etc.).
Universal solution:
1. Find the depth/height of the pointed node in the tree.
2. Perform a pre-order traversal over the tree. We return the first node we obtain at the depth/height obtained in the step 1.
public Node findLeftMost(int data) {
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while (!q.isEmpty()) {
Node temp = q.poll();
if (temp != null) {
if (temp.leftNode != null) {
if (temp.leftNode.nData == data)
return temp.leftNode;
else {
q.add(temp.leftNode);
}
}
if (temp.rightNode != null) {
{
if (temp.rightNode.nData == data) {
return temp.leftNode;
} else {
q.add(temp.rightNode);
}
}
}
}
}
return null;
}
c# implementation.
private static Node Find( Node node ) {
if ( node.Parent != null ) {
_counter = _counter + 1 ?? 1;
return Find( node.Parent );
}
return InOrder( node );
}
private static Node InOrder( Node node ) {
if ( _counter == 0 || _counter == null ) {
return node;
}
if ( node.LeftChild != null && !Visited.Contains( node.LeftChild ) ) {
_counter--;
return InOrder( node.LeftChild );
}
if ( node.RightChild != null && !Visited.Contains( node.RightChild ) ) {
_counter--;
return InOrder( node.RightChild );
}
Visited.Add( node );
_counter++;
return InOrder( node.Parent );
}
static readonly HashSet<Node> Visited = new HashSet<Node>();
private static int? _counter = null;
void display_same_level(struct btree **b) {
deque< struct btree* > dtree;
if(*b)
dtree.push_back(*b);
int level=0;
int element_at_level=1;
while(!dtree.empty() ) {
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
element_at_level--;
if(element_at_level == 0) {
level++;
}
if(t->left) {
dtree.push_back(t->left);
element_at_level++;
}
if(t->right) {
dtree.push_back(t->right);
element_at_level++;
}
}
}
First track the level of the node and add parent pointer in your tree structure.
static void LeftMostNodeSameLevel(Node myNode)
{
int level = 0;
while (myNode.Parent!=null)
{
myNode = myNode.Parent;
level += 1;
}
while (myNode!=null && level>0)
{
if (myNode.LeftNode != null)
myNode = myNode.LeftNode;
else
myNode = myNode.RightNode;
level-=1;
}
Console.WriteLine("Left Most Node is {0}",myNode.Value);
}
node* lowestInLevel(node* current) { int level = 0; node* root = current; while(root->parent != null) { root = root->parent; level++; } return findleftmostatlevel(root,level); } node * findleftmostatlevel(node * root,int level) { if(level == 0) return root; if(!root->left && !root->right) return NULL; node * temp = findleftmostatlevel(root->left,level-1); if(temp) return temp; else return findleftmostatlevel(root->right,level-1);}
- Anonymous December 10, 2015