[코딩인터뷰 완전정복] 4.6 후속자

Q : 이진 탐색 트리에서 주어진 노드의 '다음' 노드(중위 후속자(in-order successor))를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자.

// Node.h
template <class T>
class TreeNode{
public:
	T data;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;

	TreeNode(T data) {
		this->data = data;
	}
    
	void addLeft(TreeNode<T>* left) {
		this->left = left;
		left->parent = this;
	}

	void addRight(TreeNode<T>* right) {
		this->right = right;
		right->parent = this;
	}
};

#include <iostream>
#include "Node.h"

TreeNode<int>* findNextode(TreeNode<int>* pre) {
	
	if (pre->left != NULL) return pre->left;
	if (pre->right != NULL) return pre->right;

	while (pre->parent != NULL && pre == pre->parent->right) pre = pre->parent;
	if (pre->parent == NULL) return NULL;
	pre = pre->parent;
	while (pre->parent != NULL && pre->right == NULL) pre = pre->parent;
	if (pre->right == NULL) return NULL;
	else return pre->right;
}

int main() {
	TreeNode<int> a(10);
	TreeNode<int> b(5);
	TreeNode<int> c(15);
	TreeNode<int> d(3);
	TreeNode<int> e(7);
	TreeNode<int> f(13);
	TreeNode<int> g(17);
	TreeNode<int> h(1);
	TreeNode<int> i(4);
	TreeNode<int> j(6);
	TreeNode<int> k(8);
	TreeNode<int> l(11);
	TreeNode<int> n(12);

	a.addLeft(&b);
	a.addRight(&c);
	b.addLeft(&d);
	b.addRight(&e);
	c.addLeft(&f);
	c.addRight(&g);
	d.addLeft(&h);
	d.addRight(&i);
	e.addLeft(&j);
	e.addRight(&k);
	f.addLeft(&l);
	l.addRight(&n);

	TreeNode<int>* start = &a;
	while (start != NULL) {
		printf("%d - ", start->data);
		start = findNextode(start);
	}
}

주어진 Node에 대하여

1. Node의 left가 있는지 확인한다. -> 있다면 left 반환
2. Node의 right가 있는지 확인한다. -> 있다면 right 반환
3. Node가 parent의 right인지 확인한다.
    3.1. parent가 nullptr일 경우 마지막 노드이다. null을 반환한다.
    3.2. right일 경우 Node를 parent노드로 바꾸고 3을 반복한다.
    3.3 left일 경우 Node를 parent노드로 바꾸고 다음으로 넘어간다.
4. Node의 right가 있는지 확인한다.
    4.1 right가 있다면 right를 반환한다.
    4.2 right가 nullptr이고, parent도 nullptr이면 마지막 노드이다. null을 반환한다.
    4.3 right가 nullptr이고, parent가 있을 경우 Node를 parent로 바꾸고 4를 반복한다.