_987. Vertical Order Traversal of a Binary Tree.md

987. Vertical Order Traversal of a Binary Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 12, 2024

Last updated : July 01, 2024

---

Related Topics : Hash Table, Tree, Depth-First Search, Breadth-First Search, Sorting, Binary Tree

Acceptance Rate : 50.45 %

---

Solutions

• h987 v2 Lambda Sort By 2 Cols.py
• h987 v3 Removed Heaping.py
• h987.py

Python

h987 v2 Lambda Sort By 2 Cols.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        toVisit = deque([(0, 0, root)])     # (col, height, node)
        output = {}                         # key=col, val = (height, node.val)

        while toVisit :
            col, height, current = toVisit.popleft()
            if not current :
                continue

            if col in output :
                heapq.heappush(output[col], (height, current.val))
            else :
                output[col] = [(height, current.val)]

            toVisit.append((col - 1, height + 1, current.left))
            toVisit.append((col + 1, height + 1, current.right))

        return [[y[1] for y in sorted(output.get(x), key=lambda l: (l[0], l[1]))] for x in sorted(output.keys())]

h987 v3 Removed Heaping.py

# V2 was still using heapq which was now redundant since we sort either way at nlogn
# Though it seems it may ever so slighly be slower? Need to run side-by-side tests to confirm

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        toVisit = deque([(0, 0, root)])     # (col, height, node)
        output = {}                         # key=col, val = (height, node.val)

        while toVisit :
            col, height, current = toVisit.popleft()
            if not current :
                continue

            if col in output :
                output[col].append((height, current.val))
            else :
                output[col] = [(height, current.val)]

            toVisit.append((col - 1, height + 1, current.left))
            toVisit.append((col + 1, height + 1, current.right))

        return [[y[1] for y in sorted(output.get(x), key=lambda l: (l[0], l[1]))] for x in sorted(output.keys())]

h987.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        toVisit = deque([(0, 0, root)]) # (col, height, node)
        output = {}

        while toVisit :
            col, height, current = toVisit.popleft()
            if not current :
                continue

            if col in output :
                heapq.heappush(output[col], (height * 1000 + current.val, current.val))
            else :
                output[col] = [(height * 1000 + current.val, current.val)]

            toVisit.append((col - 1, height + 1, current.left))
            toVisit.append((col + 1, height + 1, current.right))

        return [list((y[1] for y in sorted(output.get(x)))) for x in sorted(output.keys())]