Chapter 11: Tree Challenges

Challenge 1: Print a tree in level order

레벨(level)을 기준으로 tree의 모든 value를 순서대로 출력한다. 동일한 레벨의 node는 동일한 line에 출력해야 한다. 예를 들면 다음과 같다.

 

알고리즘의 출력은 다음과 같아야 한다.

15
1 17 20
1 5 0 2 5 7

 

Solution

node를 level 순서대로 출력하는 간단한 방법은 큐(Queue)를 사용하여 레벨 순서 순회(Level-order traversal)을 구현하는 것이다. 까다로운 부분은 개행을 언제해야 하는지 결정하는 것이다. 

func printEachLevel<T>(for tree: TreeNode<T>) {
    var queue = Queue<TreeNode<T>>() //Queue를 사용한다.
    var nodesLeftInCurrentLevel = 0 //남은 노드의 수 추적
    queue.enqueue(tree)
    
    while !queue.isEmpty { //Queue가 빌 때까지 순회한다.
        nodesLeftInCurrentLevel = queue.count //queue의 현재 요소 수를 설정한다.
        
        while nodesLeftInCurrentLevel > 0 { //nodesLeftInCurrentLevel 만큼 반복
            guard let node = queue.dequeue() else { break } //dequeue
            
            print("\(node.value) ", terminator: "") 
            //dequeue한 요소를 출력한다. 개행 없이 출려된다.
            
            node.children.forEach { queue.enqueue($0) } 
            //dequeue된 요소의 children을 모두 queue에 넣는다.
            nodesLeftInCurrentLevel -= 1
        }
        
        print() //개행
    }
}

이 알고리즘의 시간 복잡도는 O(n) 이다. Queue를 컨테이너로 초기화하므로, 공간 복잡도 또한 O(n) 이 된다.

---

Challenge 2: Parents and ownership

트리 노드의 정의를 살펴보면, 다음과 같다.

public class TreeNode<T> {
    public var value: T
    public var children: [TreeNode] = []
    
    public init(_ value: T) {
        self.value = value
    }
}

여기에 ownership를 고려해, 부모(상위, parent) node를 포함하도록 수정한다.

 

Solution

TreeNode에 부모(parent) 속성을 추가한다.

public class TreeNode<T> {
    public var value: T
    public weak var parent: TreeNode? //추가
    public var children: [TreeNode] = []
    
    public init(_ value: T) {
        self.value = value
    }
}

Root에는 parent가 없으므로 optional로 선언해야 한다. reference cycle을 피하기 위해 weak으로 선언한다. 일반적으로 node는 하위 항목들과는 강력한 소유 관계(strong ownership relationship)를 가지지만, 상위 항목과는 관계가 약하다(weak). 이렇게 parent를 포함하는 node는 이중 연결 리스트(doubly linked list)와 유사하다. 오버헤드에 주의해야 하지만, 트리를 상향으로 순회해야 할 때 빠르게 이동할 수 있다.