Depth of binary tree

Question

I have created a class with Node:

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

And fill the tree with some data, I want depth of a tree without recursion:

def depth(self, data):
    self.depth = dict()
    root = self.dict[self.root] # this works, I got the root, it is declared in another init
    if root.data == data:
        return 0
    q = set()
    q.add(0)
    q.add(root)
    while q:
        element = q.pop()
        if type(element) == int: 
            if q == set():      
                break
            else:
                key = element
                q.add(element+1)
        else:
            v = element
            try:
                self.depth[v.data].add(key)
            except KeyError:
                self.depth[v.data] = key
            if v.right is not None:
                q.add(v.right)
            if v.left is not None:
                q.add(v.left)
            if data == v.data:
               break
    return self.depth[data]

This code should return the depth of element data. It works with lists, but I have timeout with them so I must use set instead. With sets it gets wrong results. (For example 19 instead of 6)

Why do you not want to use recursion to find the depth of the tree? — EvenLisle
– EvenLisle, Commented Apr 17, 2015 at 8:49
Code is tested by a huge ammount of Nodes, where is reached the maximum recursion. — Jonatan
– Jonatan, Commented Apr 17, 2015 at 8:52
Could you explain the meaning of q? You put different types of things in it, namely numbers and Nodes. — mkrieger1
– mkrieger1, Commented Apr 17, 2015 at 8:59
If you're not going to use recursion, then just use a stack. — Nafiul Islam
– Nafiul Islam, Commented Apr 17, 2015 at 9:01
That 0 means depth in integer, If type of element is int than it goes +1 and if type is Node than, load left,right and save the depth into dict. — Jonatan
– Jonatan, Commented Apr 17, 2015 at 9:02

Community · Accepted Answer · 2017-05-23 12:14:22Z

0

I translated this answer into Python:

def maxdepth(r):
    depth = 0
    wq = []
    path = []
    wq.append(r)
    while wq:
        r = wq[-1]
        if path and r == path[-1]:
            if len(path) > depth:
                depth = len(path)
            path.pop()
            wq.pop()
        else:
            path.append(r)
            if r.right is not None:
                wq.append(r.right)
            if r.left is not None:
                wq.append(r.left)
    return depth

edited May 23, 2017 at 12:14

CommunityBot

11 silver badge

answered Apr 17, 2015 at 13:54

Vaibhav Sagar

2,28617 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Depth of binary tree

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related