문제 // 자료구조 // 트리(Tree) // 후속자 // toJava

package question.treegraph;

/**
 * [후속자]
 *  이진탐색트리에서 주어진 노드의 다음노드(중위 후속자, in-order-successor)를 찾는 알고리즘
 *  각 노드에 부모 노드를 가리키는 링크가 존재
 *
 * [풀이]
 *  => 중위후속자가 무엇인가 ?
 *      => 중위순회를 진행할때 다음에 나올 노드
 *  => while(true) { 부모의 오른쪽 노드의 왼쪽 자식 노드, 없다면 부모로 올라감 }
 *  => 부모노드의 참조값을 가지고 있어야함
 * */

public class Q06 {

    /* main */
    public static void main(String[] args) {

        // @Test
        Node rootB = new Node(4);
        rootB.left = new Node(2);
        rootB.left.parent = rootB;
        rootB.right = new Node(6);
        rootB.right.parent = rootB;
        rootB.left.left = new Node(1);
        rootB.left.left.parent = rootB.left;
        rootB.left.right = new Node(3);
        rootB.left.right.parent = rootB.left;
        rootB.right.left = new Node(5);
        rootB.right.left.parent = rootB.right;
        rootB.right.right = new Node(7);
        rootB.right.right.parent = rootB.right;

        // == 중위후속자 ==
        System.out.println(getNextInOrder(rootB.left.right).data/*3*/); // -> 4
    }

    /* Node */
    static class Node {
        int data;
        Node parent;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
        }
    }

    /* getNextInOrder */
    public static Node getNextInOrder( Node node ) {
        if( node == null ) return node;

        // == 오른쪽 ==
        if( node.right != null ) {
            // == 오른쪽자식존재 -> 오른쪽에서 제일왼쪽노드 반환 ==
            Node n = node.right;
            if(n == null) return null;
            while(n.left != null) {
                n = n.left;
            }
            return n;
        }
        // == 위로 ==
        else {
            // == 오른쪽이 아닌 왼쪽이 있을 때까지 위로 올라감 ==
            Node me = node; // me
            Node parent = me.parent; // parent
            while (parent != null && parent.left != me) {
                me = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }
}