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

  • dansummer94 + 1 comment
    • 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')
    • tbhesswebber + 0 comments

      I'm a JS guy, so handling the trees in Python has been a learning experience. I had no idea that print had additional params, so my solution ended up being rather convoluted, building a list of dictionaries that track node.info and vertical and horizontal offsets, eventually gets sorted, and then gets mapped to an array of strings that is joined and printed. It was nasty. Haha

      Thanks!