CareerCup

Apart from doing BFS you can use recursion also. The main idea is to remember the level visited for the first time so the you dont print the nodes of the same level when you visit them later.

int visited = -1;
void LeftMostInEveryLevel (struct node *root, int level) {
     if (root != NULL) {
              if (level > visited) {
                        cout << "Level = " << level << ", Node = " << root->data << endl;
                        visited = level;
              }
              LeftMostInEveryLevel (root->left, level + 1);
              LeftMostInEveryLevel (root->right, level + 1);
     }
}

Varun,

Please help me to understand the logic?

I think we recursively go to each level until we find a null root, but what I am wondering is the exit condition.

When you find a null root, how can we print root->key??

So basically we keep going left until we find a leaf node rather than checking for null? In that case we print only left most leaf node?

Best Regards,
Sai

But, the requirement is leftmost at *each level*, not just the leftmost.

This sounds to me like it requires a bread-first search, but I'm not sure how to adapt that to keep track of the level the nodes are on, and don't really have time to think/solve atm.

This python might do it, test included:

import sys

class Node:
  def __init__(self,data):
    self.right = None
    self.left = None
    self.data = data

class Tracker:
  def __init__(self,data,dist):
    self.data = data
    self.dist = float(dist)

def leftNodes(n,lvl,q,dist):
  if n.left:
    if len(q) < lvl + 1:
      q.append(Tracker(n.left.data,dist))
    elif q[lvl].dist > dist:
      q[lvl] = Tracker(n.left.data,dist)
    leftNodes(n.left,lvl + 1,q,dist)
  if n.right:
    if len(q) < lvl + 1:
      q.append(Tracker(n.right.data,dist + 1.0/(lvl+1)))
    elif q[lvl].dist > dist:
      q[lvl] = Tracker(n.right.data,dist + 1.0/(lvl+1))
    leftNodes(n.right,lvl + 1,q,dist + 1.0/(lvl+1))

def main():
  root = Node(1)
  root.left = Node(2)
  root.right = Node(3)
  root.left.left = Node(4)
  root.left.right = Node(5)
  root.right.left = Node(6)
  root.right.right = Node(7)
  root.right.left.left = Node(8)
  root.right.left.right = Node(9)
  root.right.left.right.left = Node(10)
  root.right.left.right.right = Node(11)
  q = []
  leftNodes(root,0,q,0)
  for i in q:
    print i.data

if __name__ == "__main__":
    sys.exit(main())

struct Node
{
int data;
struct Node *left;
struct Node *right;
struct Node *next;
};
struct Node *NewNode(int data)
{
struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
temp->data=data;
temp->next=NULL;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void LeftMostOnEachLevel(struct Node *&node)
{
if(!node)
return;
queue<struct Node *> myqueue;
myqueue.push(node);
myqueue.push(NULL);
while(true)
{
struct Node *temp=myqueue.front();
myqueue.pop();
if(temp)
{
temp->next=myqueue.front();
if(temp->right)
myqueue.push(temp->right);
if(temp->left)
myqueue.push(temp->left);
}
else
{
if(!myqueue.empty())
myqueue.push(NULL);
else
break;
}
}
}
void Traversal(struct Node *node)
{
if(!node)
return;
struct Node *temp=node;
while(temp->next)
temp=temp->next;
cout<<temp->data<<endl;
if(node->right)
Traversal(node->right);
else if(node->left)
Traversal(node->left);
}
int main()
{
struct Node *node=NewNode(1);
node->left=NewNode(2);
node->right=NewNode(3);
node->left->left=NewNode(4);
node->left->right=NewNode(5);
node->right->right=NewNode(6);
LeftMostOnEachLevel(node);
Traversal(node);
getchar();
return 0;
}

public static void printLeftNode(TreeNode pNode, HashMap<Integer, Boolean> map, int currenDepth){
		if(pNode == null){
			return;
		}

		if(!map.containsKey(currenDepth)){
			System.out.print(pNode.data + "  ");
			map.put(currenDepth, true);
		}
		
		printLeftNode(pNode.pLeft, map, currenDepth + 1);
		printLeftNode(pNode.pRight, map, currenDepth + 1);
	}

I think at least we should traverse all the nodes in this tree, we cannot only keep the information of a single node in each level because if this node do not have child nodes then we have to look for other nodes who have child nodes at this level. My strategy is to print each level of this tree with 2 queues( 1 queue also works). The running time is O(n). Please let me know if there is a O(log(n)) solution.

do a travelsal on the tree and record the level when each node get visited. If this node is the first node get visited on this level, then this node is the leftmost node.

void visit(Node *node, int level) // level=0 at the time of invocation 
{
	if(b == NULL)
		return;
	else
	{
		if(map[level] == false)
		{
			map[level] = true
			printf("Level:%d, Value%d\n", level, node->data)
		}
		visitLeft(node->left,level+1);
		visitRight(node->right, level+1)
	}
}

void visit(TreeNode *root)
{
	if (root == NULL)
		return;

	std::vector<TreeNode*> q,q1;
	std::vector<TreeNode*> q1;

	std::vector<TreeNode*> *pq = &q;
	std::vector<TreeNode*> *pq1 = &q1;

	pq->push(root);
	while (!pq->empty())
	{
		printf(pq->at(0)->val);
		
		for (size_t i=0; i<pq->size(); ++i)
		{
			TreeNode *n = pq->at(i);
			if (n->left)
				pq1->push_back(n->left);
			if (n->right)
				pq1->push_back(n->right);
		}
		pq->clear();
		std::swap(pq,pq1);
	}
}

void bfs(TreeNode* root)
{
        queue< pair<TreeNode*, int> > q;
        int pLevel(0), cLevel;
        TreeNode* cNode;
        if (root != NULL) q.push( make_pair(root, 1) );
        while (!q.empty())
        {
             cNode = q.front().first;
             cLevel = q.front().second;
             q.pop();
             
             if (cLevel != pLevel) cout << cNode->val << endl;
             pLevel = cLevel;
             
            if (cNode->left) q.push( make_pair(cNode->left, cLevel+1) );
            if(cNode->right) q.push( make_pair(cNode->right, cLevel+1) ); 
            
        }
}

public List<T> lefmostAtEachLevel(){
		
		if( isEmpty() ){
			return new ArrayList<>();
		}
		
		List<T> res = new ArrayList<>();
		
		Queue<NodeLevel<T>> levelQueue = new ArrayDeque<>();
		levelQueue.add( new NodeLevel<>(root, 0) );
		int prevLevel = -1;
		
		while( ! levelQueue.isEmpty() ){
			
			NodeLevel<T> nodeLevel = levelQueue.poll();
			
			if( nodeLevel.level != prevLevel ){
				res.add( nodeLevel.node.value );
				prevLevel = nodeLevel.level;
			}
			
			for( Node<T> child : nodeLevel.node.children ){
				levelQueue.add( new NodeLevel<>(child, nodeLevel.level+1) );
			}
			
		}
		
		return res;
	}

How about just doing breadth first traversal (level order) and just print only first node at each level.

Do the level order traversal. Print first element after each level change.

int leftMostBinaryTree(struct BinaryTreeNode *root)
{
if(!root) return 0;
struct Queue *Q=CreateQueue();
EnQueue(Q,root);
EnQueue(Q,NULL); //end of first level

while(!IsEmptyQueue(Q)){
  root = DeQueue(Q);
  if(root == NULL) {  
    if(!IsEmptyQueue(Q))  //Put another marker for next level
      EnQueue(Q,NULL);
      if(root->left)                //Print left Most element
        print("%d",Q->left);
  }
  else{
  if(root->left)
     Enqueue(Q,root->left);
   if(root->right)
     Enqueue(Q,root->right);
 }
}
}

Noticed most of you are assuming a binary tree. The question doesn't state that. My version in javascript:

function Node(val){
  this.value = val;
  this.children = [];
}

function printLefts(root){
  var queue = [];
  var node;
  var children;
  var i;
  var previousHeight;
  var child;
  root.height = 0;
  queue.push(root);

  while(queue.length > 0){
    node = queue.shift();
    if(node.height !== previousHeight){
      console.log(node.value);
    }
    children = node.children;
    for(i=0;i<children.length;i++){
      child = children[i];
      child.height = node.height + 1;
      queue.push(child);
    }
    previousHeight = node.height;
  }
}

Not my most elegant piece of code. Would love to hear how you would improve this. Linear in number of elements (BF).

void printLeftmostElements(node *root){
    std::queue<node *> queue;
    queue.push(root);
    int current_level = 1, next_level = 0;
    
    std::cout << root->info << " ";
    while(!queue.empty()){
        node *current = queue.front();
        queue.pop();

        if (current->left){
            ++next_level;
            queue.push(current->left);
        }
        if(current->right){
            ++next_level;
            queue.push(current->right);
        }

        if (--current_level == 0 && next_level > 0){
            std::cout << queue.front()->info << " ";
            current_level = next_level;
            next_level = 0;
        }
    }
}

void BFS() {
	int i, j, k;

	q.push_back(1), r.push_back(1);
	done[1] = true;
	niv[1] = 1;

	for (i = 0; i < q.size(); i++) {
		k = q[i];
		for (j = 0; j < L[k].size(); j++) {
			q.push_back( L[k][j] );
			niv[ L[k][j] ] = niv[k] + 1;
			if (!done[ niv[ L[k][j] ] ]) r.push_back(L[k][j]);
			done[ niv[ L[k][j] ] ] = true;
		}
	}

	for (i = 0; i < r.size(); i++)
		printf("%d ", r[i]);
}

void LeftMost_Levelwise(struct bst *b, int level) // level=0 at the time of invocation 
{
	if(b)
	{
		if(b->lc!=NULL)
			printf("Level:\t%d Value:\t%d\n",level,b->lc->data);
		LeftMost_Levelwise(b->lc,level+1);
		LeftMost_Levelwise(b->rc,level+1);
	}
}

void printLeft(tree * root)
{
	static int level = -1;

	level++;
	if (root == NULL)
	{
		printf("\nAtLevel: %d, Key:%d", level, root ? root->key : 0);
		
	}
	if (root->left)
	{
		printLeft(root->left);
	} 
	else printLeft(root->right);
}