Print the BST in level order

Question

Sigiloso · Accepted Answer

if not tree:
        return
    nodes=collections.deque([tree])
    currentCount, nextCount = 1, 0
    while len(nodes)!=0:
        currentNode=nodes.popleft()
        currentCount-=1
        print currentNode.val,
        if currentNode.left:
            nodes.append(currentNode.left)
            nextCount+=1
        if currentNode.right:
            nodes.append(currentNode.right)
            nextCount+=1
        if currentCount==0:
            #finished printing current level
            print '
',
            currentCount, nextCount = nextCount, currentCount

Sigiloso · Answer

Basic idea: perform a breadth first traversal of the tree. Every time you dequeue a node, print it. This will give a level order print in linear time.

Sigiloso · Answer

Recursive function that starts at the root and recursively prints the value of each left and right node, along with the level order.

bstprint(node, count) {
    if (node == null) {
        return;
    }
    print count + ": " + node.value;  //pseudocode for printing cause lazy
    bstprint(node.left, count + 1);
    bstprint(node.right, count + 1);
}

bstprint(root, 0); //initial call

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas