https://www.acmicpc.net/problem/9934
So the question describes an inorder traversal from left->root->right.
So I was thinking of adding the level of nodes logic to the impl of this traversal until I drew the tree graph and found out that
1 6 4 3 5 2 7
^ ^ ^
m r m
The middle of the original list is the root (always) and if you divide the list each time, the mid point is the middle point (root of subtree)
So i figured out the pattern but I really didnt kno how to implement this. So I googled and this was a divide and conquer question.
Remember dfs and backtracking?https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-10819%EB%B2%88-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%B5%9C%EB%8C%80%EB%A1%9C
Whenever you have a range of choices, you can call dfs multiple times to fully traverse the possibilities. So let's divide the list into 2 and call dfs that searches the lower and upper half. The breaking condition would be if start==end, that means we are at leaf so we append them at respective level and return. Rmb return is needed for backtracking cuz if not it will continue to the other logic.
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
import math
h=int(input())
lst = list(map(int,input().split()))
ans = defaultdict(list)
def dfs(start,end,level):
if start==end:
ans[level].append(lst[start])
return
mid = (start+end) //2
ans[level].append(lst[mid])
dfs(start,mid-1,level+1)
dfs(mid+1,end,level+1)
dfs(0,len(lst)-1,0)
for key in ans:
print(*ans[key])
yes so it is like the bracket question and after solving some leetcode tree questions, I kinda get it better now.
I managed to think of incrementing levels but i wanst gonna use start and end pointers but like the length of list to be sliced. If length is 1 then it is a leaf node, in which case we append it to the respective level. But this pointer way is better cuz slicing is ineff.
2^n cuz there are 2 choices - searching lower and upper half?
n space
NOPE this is a binary search so
The provided code performs a binary tree traversal and prints the nodes at each level. The time complexity of this code is O(n), where 'n' is the number of elements in the lst
. This is because the code processes each element in the list exactly once.
Here's a breakdown of the code's complexity:
The dfs
function recursively divides the list in half at each level of the tree until it reaches a base case where the start and end indices are the same (i.e., a single element is processed). This division is done using binary search techniques, which ensures that each element is visited exactly once. The number of levels in the recursion is determined by the height of the binary tree, which is logarithmic in 'n' for a balanced binary tree.
At each level of the binary tree, the dfs
function appends the element at the midpoint of the current range to the ans
dictionary, which groups elements by level.
After the traversal, the code prints the elements at each level. The loop that iterates over the ans
dictionary and prints the elements at each level has a time complexity of O(n) because it iterates over each element exactly once.
Overall, the time complexity of the code is dominated by the O(n) traversal of the lst
, making it O(n) in total. The space complexity is also O(n) because the ans
dictionary stores elements grouped by level, and in the worst case, each element in lst
could belong to a different level.