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

  • dansummer94
     + 2 comments
    • I assume one recent update has change the code and answer for python 3.
    • The desired output has changed from only the nodes on the 'single-direction-branches' to all the nodes you can see from the top, thus a lot of the posted codes is not valid.
    • I'm not sure if I can optimize the while part of my code, and I would prefer a version without recursion in python, but the code below is all I can post at the moment.
    def topView(root):
    # deal with empty tree case
    if root == None: return
		
    # tuple (pos, lvl, node.info)
    tupleList = [(0,0,root.info)]
    tupleAppend(tupleList, root.left, 0, 0, 'L')
    tupleAppend(tupleList, root.right, 0, 0, 'R')

    # select tuples with lowest lvl for each pos
    tupleList.sort(key = lambda tup: (tup[0], tup[1]))
    i = 0
    while i < len(tupleList) - 1:
        while tupleList[i][0] == tupleList[i + 1][0]:
            tupleList.pop(i + 1)
            if (i + 1) > len(tupleList) - 1: break
        i += 1
    
    for _, _, data in tupleList: print(data, end = " ")

def tupleAppend(ls, node, pos, lvl, direction):
    if node:
        if direction == 'L': pos = pos - 1
        elif direction == 'R': pos = pos + 1
        lvl = lvl + 1
        ls.append((pos, lvl, node.info))
        tupleAppend(ls, node.left, pos, lvl, 'L')
        tupleAppend(ls, node.right, pos, lvl, 'R')