We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

  • avramsmart + 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 + 1 comment

      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.

      • renato314159 + 1 comment

        Trying to decipher some of your logic (thanks for the comments, they're a huge help).

        what is happening in this line?

        for _ in range(len(this_level)):
    node, score = this_level.pop(0)

        Thanks

        • gelmilorenzo + 2 comments

          Each time the while begins, I expects all and only the nodes of a single level to be in this_level. 

          for _ in range(len(this_level)):

          This line allows me to iterates only on the nodes in a single level, as their amount is the initial length. If _ confuses you, it's just a convention symbol that states you don't need and won't use the corresponding variable, in this case the loop index.

          node, score = this_level.pop(0)

          The pop function removes the first element of the list. I remove the first since I am going to extend the list with the next level. As the element I am going to pop is a tuple, I can assign both variable on a single line, thanks to Python sintax.

          Feel free to keep asking! :)

          • renato314159 + 0 comments

            okay, i finally understand it.

            Thank you so much!

          • renato314159 + 1 comment

            wait no, sorry, one last thing. 

            this_level.extend()

            why use extend instead of append?

            I used a similar solution with the level order traversal one but used append instead.

            • gelmilorenzo + 0 comments

              Extend is more suitable (and faster) when you need to "append" more than one thing at a time (any iterable). Since I need to add two items (left and right), it is preferable.

              N.B.: I could also have used a simple "+=" (which is infinitesimally faster), but this is more explicit and I prefer it for such things.