Write a program to find depth of binary search tree without using recursion

Question

userisyo · Accepted Answer

Python implementation using a stack.



def depth(root):
    st = [(root, 0)]
    maxd = 0
    while len(st):
        node, dpt = st.pop()
        maxd = max(maxd, dpt)
        if node['left']:
            st.append((node['left'], dpt + 1))
        if node['right']:
            st.append((node['right'], dpt + 1))
    return maxd

Anonymous · Answer

Q.enqueue rootNode,1
depth=0
while q,count>0
   [n,d] = q.dequeue
   depth = max(d,depth)
   if n.left   q.enqueue(n.left,d+1)
   if n.right  q.enqueue(n.right, d+1)
end
return depth

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches