Discussion on Tree : Top View Challenge

avramsmart 7 months ago+ 1 comment

Yep this is true, we now have to worry about all nodes, not just one on the sides. Also you have to sort them by levels. This is my solution in Python.

def topView(root):
    uniq_lvls = []
    q = Queue()
    q.put((root, 0))
    
    while not q.empty():
        temp = q.get()
        if temp[1] not in (i[1] for i in uniq_lvls):
            uniq_lvls.append(temp)
        if temp[0].left:
            q.put((temp[0].left, temp[1]-1))
        if temp[0].right:
            q.put((temp[0].right, temp[1]+1))
    for x in sorted(uniq_lvls, key=lambda e: e[1]):
        print(x[0].info, end=' ')

I am open to your suggestions of how I can improve speed and particularly memory consumption.

gelmilorenzo 7 days ago+ 0 comments

Hi, this seemed quite faster in a couple benchmark I ran. The main difference is the usage of dictionaries (that probably can check for items faster than in your code, to check for existence) and the queue removal. Also, the "node, score" assignation avoid some indexing I believe...

def topView(root):
    # Initialize the level
    this_level = [(root, 0)]
    scores = {}
    while this_level:
        # Basically iterate over the nodes on a single level
        for _ in range(len(this_level)):
            node, score = this_level.pop(0)
            # Skip empty nodes
            if not node:
                continue
            # Store the score if it's a new one!
            if score not in scores:
                scores[score] = node.info
            # Add the node children to the next level
            this_level.extend(
                [(node.left, score - 1),
                (node.right, score + 1)])

    # Sort the scores and print their values 
    # (By default the sort is on the tuple first element: the score)
    for _, value in sorted(list(scores.items())):
        print(value, end=' ')

Good coding.