Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time.

Question

Ja · Accepted Answer

So we all know the recursive method:

void traverse(Node* head)
{
    if (head)
    { 
        cout data left);
        traverse(head->right);
    }
}

A non recursive version might look like:

void traverse(Node* head)
{
    //a stack implementation - choose your favorite
    Stack stack;
    stack.push(head);

    while ( !stack.empty() )
    {
        Node* current = stack.pop();        
        if (current)
        {
             cout data left);
             stack.push(current->right);
         }        
    }
}

H. Abajyan · Answer

node = root;
passed = "Not passed"; // 0 = "Not Passed", 1 = "left subtree passed", 2 = "right subtree passed too"

while (true)
{

switch (passed) 
{
	case "Not Passed":
		traverse(node);
		if (node.left != null) 
		{
			node = node.left;
		} else 
		if (node.right != null)
		{
			node = node.right;
		} else // reached to a leaf
		{			
			if (node == root)
				break; // Done traversal
			passed = "right subtree passed too";
		}
		
	case "left subtree passed":
		if (node.right != null) 
		{
			node = node.right;
			passed = "Not passed";
		} else
		{
			passed = "right subtree passed too";
		}

	case "right subtree passed too":
		if (node.parent == null) // same as to check that node == root
			break; // Done traversal
		if (node.parent.left == node)
			passed = "left subtree passed";
		else //right
			passed = "right subtree passed too";
		node = node.parent;
}
}

**************
Since algorythm passes through each vertex of the tree only one time and thru each edge - not more than 

two times, and since edge count in a tree is always less than the vertex count (n)
the application run-time is O(n). it is obvious that memory is constant.
**************

Anonymous · Answer

Threaded binary trees.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas