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.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

  • HHWWHH
     + 4 comments

    I am a beginner. If I found this place earlier, I would have not spent hours on this unclarified 'easy' question and doubt myself...... In conclusion, two interpretations on this question: 1. Just like what @thedurphy said, this interpretation of top view aligns with this Youtube video and GFG. And code in Python can be like this (Although it does not pass all tests, it aligns with first interpretation):

    def topView(root):
    from collections import defaultdict
    queue=[(root,0)]
    hashtable=defaultdict(lambda:[]) 
    for node,level in queue: #level=x-coordinator
        if node!=None:
            hashtable[level].append(node.data) #hashtable, collect node data with the same level#
            queue.extend([(node.left,level-1),(node.right,level+1)]) #add node in sublevel to queue
    if hashtable !=None:
        for level in xrange(min(hashtable.keys()),max(hashtable.keys())+1):
            print hashtable[level][0], #TOPVIEW
    else:
        return None
    1. Another interpretation is provided by @trideceth12, which is aligned with all test cases. Although I doubt this interpretation, I still created the Python code for it: 
    def topView(root):
    #start with left most leaf
    if root.left:
        printleftside(root.left) #print left side top view, from bottom to top (left to right)
    print root.data, #print root
    if root.right:
        printrightside(root.right) #print right side top view, from top to bottom (left to right)

def printleftside(node):
    if node:
        printleftside(node.left)
    else:
        return
    print node.data,

def printrightside(node):
    if node:
        print node.data,
        printrightside(node.right)
    else:
        return

    In the end, WHAT do we use TOPVIEW for in terms of both interpretations?