[백준] 5639번: 이진 검색 트리

https://www.acmicpc.net/problem/5639

initial

So we are given the pre-order path (root,left,right) and we want to give answer for post-order path(left,right,root). How the fk do you do this??

I first thought of using 2**n -1 to compute the height of the tree or else my recruisve loop will keep on looping to the left or right without coming back. But then how do i implement this? Actually we dont need to with help from google.

If you observe binary tree, the nodes to the left of the root are smaller than the root and nodes to the right are bigger than the root. So we can divide into left and right subtrees recursively. When we have something like [5,17,26], we recur into the left subtree [5]. In here, there is only one node- itself. We have to do something for our recursion end condition. If we do if len(lst)==1: print(lst[0]) return it is wrong answer. (tbc idk why) Instead, when there is only 1 element left, we put all that in the left subtree.

Why? We want to deal with the case when there are no values greater than root so we want to finish dealing with the left subtree first before traversing the empty right subtree before finally printing the root (post order). Something like this below

The recursion is so hard.

solution

import sys
input = sys.stdin.readline
#recursion error 방지
sys.setrecursionlimit(10**9)
lst = []

while True:
    try:
        lst.append(int(input()))
    except ValueError:
        break

def dfs(lst):
    if len(lst)==0:
        return

    left,right=[],[]
    root = lst[0]
    for i in range(1, len(lst)):
        if lst[i] > root:
            left = lst[1:i]
            right = lst[i:]
            break
    else:
        left = lst[1:]

    dfs(left)
    dfs(right)
    print(root)

dfs(lst)

complexity

Time Complexity:

The time complexity of the loop that reads input values is O(n), where n is the number of input values.
In the dfs function, the loop iterates through the elements of the lst, and for each element, it performs some constant-time operations. Therefore, the time complexity of the dfs function is O(n) where n is the size of the input list.
The overall time complexity is O(n).

Space Complexity:

The space complexity is determined by the recursive calls in the dfs function and the additional lists (left and right).
In the worst case, the depth of the recursion is proportional to the length of the input list, so the space complexity of the recursion is O(n).
Additionally, the left and right lists store portions of the original list, and their total space is also O(n) in the worst case.
The overall space complexity is O(n).