updated bottom and top view of binary tree solution

david-legend · david-legend · commit 4d4eaad28e27 · 2023-02-21T08:41:49.000Z
diff --git a/leetcode/src/binary_trees/bottom_view_of_binary_tree/bottom_view.py b/leetcode/src/binary_trees/bottom_view_of_binary_tree/bottom_view.py
@@ -4,39 +4,35 @@ def __init__(self, val):
         self.val = val
         self.left = self.right = None
 
-# Time ( O(N) + O(WLog (W) *  KLog(k)) )
+# Time  O(N) + O(WLog W)
 # Where N is the number of nodes in the tree
 # W is the the width of the tree
-# K is the average length of nodes in the height of the tree
 
-# Space O(n) + O(n) -> O(N)
-# Where N is the number of nodes in the tree
+# Space O(N/2) + O(W)  --> O(N) + O(W)
+# Where N is the number of nodes on a particular level
+# Where W is the number of nodes spread across the with of the tree if we consider the results array
 
 def bottomView(root):
     if not root: return
 
-    vertical_order = defaultdict(dict)
-    queue = deque([(root, 0, 0)])
+    vertical_order = {}
+    queue = deque([(root, 0)])
 
     while queue:
         level_size = len(queue)
         for _ in range(level_size):
-            node, x, y = queue.popleft()
+            node, x = queue.popleft()
 
-            if x not in vertical_order:
-                vertical_order[x] = defaultdict(list)
-            vertical_order[x][y].append(node.val)
+            vertical_order[x] = node.val
 
             if node.left:
-                queue.append((node.left, x-1, y+1))
+                queue.append((node.left, x-1))
             if node.right: 
-                queue.append((node.right, x+1, y+1))
+                queue.append((node.right, x+1))
 
     result = []
     for key in sorted(vertical_order.keys()):
-        val_keys = sorted(vertical_order[key].keys())
-        bottom_view_key = val_keys[-1]
-        result.append(vertical_order[key][bottom_view_key].pop())
+        result.append(vertical_order[key])
     
     return result
 
diff --git a/leetcode/src/binary_trees/top_view_of_binary_tree/top_view.py b/leetcode/src/binary_trees/top_view_of_binary_tree/top_view.py
@@ -7,40 +7,37 @@ def __init__(self, val):
 
 
 
-# Time ( O(N) + O(WLog (W) *  KLog(k)) )
+# Time  O(N) + O(WLog W)
 # Where N is the number of nodes in the tree
 # W is the the width of the tree
-# K is the average length of nodes in the height of the tree
 
-# Space O(n) + O(n) -> O(N)
-# Where N is the number of nodes in the tree
+# Space O(N/2) + O(W)  --> O(N) + O(W)
+# Where N is the number of nodes on a particular level
+# Where W is the number of nodes spread across the with of the tree if we consider the results array
 
 
 def topView(root):
     if not root: return
 
     vertical_order = defaultdict(dict)
-    queue = deque([(root, 0, 0)])
+    queue = deque([(root, 0)])
 
     while queue:
         level_size = len(queue)
         for _ in range(level_size):
-            node, x, y = queue.popleft()
+            node, x = queue.popleft()
 
             if x not in vertical_order:
-                vertical_order[x] = defaultdict(list)
-            vertical_order[x][y].append(node.val)
+                vertical_order[x] = node.val
 
             if node.left:
-                queue.append((node.left, x-1, y+1))
+                queue.append((node.left, x-1))
             if node.right: 
-                queue.append((node.right, x+1, y+1))
+                queue.append((node.right, x+1))
 
     result = []
     for key in sorted(vertical_order.keys()):
-        val_keys = sorted(vertical_order[key].keys())
-        bottom_view_key = val_keys[0]
-        result.append(vertical_order[key][bottom_view_key].pop())
+        result.append(vertical_order[key])
     
     return result
 
