Given a Binary Search Tree, iterate over the elements without using recursion.

Question

leonmax · Accepted Answer

for in order traverse a tree, we use stack to store nodes on the path. (for preorder/postorder traverse, only little to be changed.)

def inorder(node):
    stack = []
    leftChecked = False
    while node != None:
        if not leftChecked and node.left != None:
            stack.append(node)
            node = node.left
        else:
            print node.data
            if node.right != None:
                node = node.right
                leftChecked = False
            elif len(stack)>0:
                node = stack.pop()
                leftChecked = True
            else:
                node = None


for breadth-first traversal, we use a queue to store untraversed children nodes

def breadthfirst(node):
    from collections import deque
    q = deque()
    if node != None:
        q.append(node)
    while len(q)>0:
        node = q.popleft()
        print node.data
        if node.left != None:
            q.append(node.left)
        if node.right != None:
            q.append(node.right)

leonmax · Answer

rechecked on pre order and post order,  not as easy as I think. The state whether right sub-tree has be visited need to be pushed into the stack along with the elements:

def preorder(node):
    stack = []
    leftChecked = rightChecked = False
    while True:
        if not leftChecked:
            yield node.data
        if not leftChecked and node.left:
            stack.append((node, False))
            node = node.left
        elif not rightChecked and node.right:
            stack.append((node, True))
            node = node.right
            leftChecked = False
        elif len(stack) > 0:
            node, rightChecked = stack.pop()
            leftChecked = True
        else:
            break;

def postorder(node):
    stack = []
    leftChecked = rightChecked = False
    while True:
        if not leftChecked and node.left:
            stack.append((node, False))
            node = node.left
        elif not rightChecked and node.right:
            stack.append((node, True))
            node = node.right
            leftChecked = False
        else:
            yield node.data
            if len(stack) > 0:
                node, rightChecked = stack.pop()
                leftChecked = True
            else:
                break;

PrinceBoroujerdi · Answer

public node* BFS(node* current, int matchNum)
    {
        Queue remainingNodes = new Queue();
        remainingNode.Insert(current);
        
        while (!remainingNodes.IsEmpty())
        {
            node* tmp = remainingNodes.Remove();

            if (temp.value == matchNum)
            {
                return tmp;
            }
            
            if (tmp->left != null)
            {
                remainingNodes.Push(tmp->left);
            }
            
            if (tmp->right != null)
            {
                remainingNodes.Push(tmp->right);
            }
        }
    }

PrinceBoroujerdi · Answer

This will simply iterate over all the nodes. Above solution will find a node.

public node* Iterate(node* current, int matchNum)
    {
        Queue remainingNodes = new Queue();
        remainingNode.Insert(current);

        while (!remainingNodes.IsEmpty())
        {
            node* tmp = remainingNodes.Remove();

            if (tmp->left != null)
            {
                remainingNodes.Push(tmp->left);
            }

            if (tmp->right != null)
            {
                remainingNodes.Push(tmp->right);
            }
        }
    }

Sem · Answer

0) {
			$elem = array_pop($queue);
			echo $elem->d . "	";
			if ($elem->l) {
				$queue[$elem->l];
			}
			if ($elem->r) {
				$queue[$elem->r];
			}
		}
	}
}

?>

Hussein · Answer

DFS using a tack data structure.

Meta

Frage im Vorstellungsgespräch bei Meta

Antworten zu Vorstellungsgespräch

Beobachtete Unternehmen

Jobsuchen