[백준] 1991번: 트리 순회

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

initial

So we are doing 3 tree traversals

whats wrong here? i keep gettign attribute error str

[Fixed] cuz you need to put tree[node.left] as parameter to your methods, not just node.left which is not an object but just an attribute of an object

but still the recursion impl is wrong see here

https://velog.io/@whitehousechef/Python-recursion

wrwong initial code:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def pre_order(node):
    if node:
        print(node.value, end='')
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node:
        in_order(node.left)
        print(node.value, end='')
        in_order(node.right)

def post_order(node):
    if node:
        post_order(node.left)
        post_order(node.right)
        print(node.value, end='')

tree = {}
n = int(input())
for i in range(n):
    n, l, r = input().split()
    if l == '.':
        l = None
    if r == '.':
        r = None
    tree[n] = Node(n, l, r)

# Perform tree traversals starting from the root node 'A'
root_node = tree['A']
print("Pre-order traversal:")
pre_order(root_node)
print("\nIn-order traversal:")
in_order(root_node)
print("\nPost-order traversal:")
post_order(root_node)

solution

correct code

the impl for the 3 traversals are diff from my wrong initial code. debug mine to see where it went wrong

[Revisited] so as mentioned in the link, recursion for my impl will return without executing below code if any of the child is None

but if we put an if statement to prevent the recursion from returning prematurely, it will wwork now. This is cuz if node.left first checks if node.left is None or not and if it is None, we go to the next if statement.

import sys
input=sys.stdin.readline

class Node:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
        
## root->left->right
def pre_order(node):
    print(node.value, end='')
    if node.left:
        pre_order(tree[node.left])
    if node.right:
        pre_order(tree[node.right])

def in_order(node):
    if node.left:
        in_order(tree[node.left])
    print(node.value, end='')
    if node.right:
        in_order(tree[node.right])

def post_order(node):
    if node.left:
        post_order(tree[node.left])
    if node.right:
        post_order(tree[node.right])
    print(node.value, end='')

tree = {}
n = int(input())
for i in range(n):
    n, l, r = input().split()
    if l == '.':
        l = None
    if r == '.':
        r = None
        ## not storing an actual object, but storing a reference to that object
    tree[n] = Node(n, l, r)

# Perform tree traversals starting from the root node 'A'
root_node = 'A'
pre_order(tree[root_node])
print()
in_order(tree[root_node])
print()
post_order(tree[root_node])

complexity

The time complexity of the tree traversal algorithms (pre-order, in-order, and post-order) in a binary tree is O(n), where 'n' is the number of nodes in the tree. This is because in the worst case, you need to visit every node exactly once.

Here's a brief explanation of the time complexity for each traversal:

1. Pre-order Traversal: In pre-order traversal, you visit the current node, then recursively visit the left subtree, and finally, recursively visit the right subtree. This results in a time complexity of O(n) because you visit each node exactly once.

2. In-order Traversal: In in-order traversal, you visit the left subtree, then the current node, and finally the right subtree. The time complexity is also O(n) as you visit each node once.

3. Post-order Traversal: In post-order traversal, you visit the left subtree, then the right subtree, and finally the current node. Once again, the time complexity is O(n) because each node is visited exactly once.

The space complexity for these recursive algorithms is determined by the maximum depth of the call stack, which is O(h), where 'h' is the height of the binary tree. In the worst case, for an unbalanced tree, 'h' can be as large as 'n', making the space complexity O(n). However, for a balanced tree, 'h' is logarithmic in 'n', leading to a space complexity of O(log n).