Find the least common ancestor of two node in binary tree

Binary Search Tree는 항상 부모 노드의 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽은 큰 값을 가지도록 설계되어져 있으므로, Binary Search Tree에서 LCA (Least Common Ancestor)는 두 값이 분기하는 노드가 LCA가 된다. 예를 들어 , 노드 4와 7의 LCA는 6이 된다. 노드 6과 4의 LCA는 6이 된다.

Copied from http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/200px-Binary_search_tree.svg.png

하지만, Binary Tree의 경우에는 이런 규칙이 없으므로, LCA를 찾기 위해 좀 더 복잡한 방법이 필요하다.

copied from http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/tree1.bmp

예를 들어 Node 1와 2의 LCA는 7이지만, Binary Search Tree에서 이용한 방법을 적용할 수 없다.

따라서, Binary Tree에서 LCA를 찾기 위한 다양한 방법을 인터넷에서 찾을 수 있다.

여기서 구현한 방법은 LinkedList를 이용하여 각 Node의 Path를 저장하고, LinkedList의 내용을 비교하면서 Node가 달라지는 시점을 LCA로 인식하는 방법이다.

예를 들어,  Node 2와 12의 LCA를 구한다고 가정한다. 그러면, Node 12의 Path가 LinkedList에서 8->5->7->12로 저장되고, Node 2의 Path가 8->5->7->12->2로 저장된다.

두 개의 LinkedList의 값을 앞에서 부터 하나씩 비교해 나가면, 12 다음부터 두 Node의 Path가 변경됨을 인식함으로, LCA는 12가 된다.

아래 코드를 재귀 호출을 이용하여 각 Node Path를 찾고, Node Path를 비교하면서 LCA를 찾는 코드이다.

    public static LinkedList findNode( Node root, int val ) {

        // root가 null이면 null을 리턴

        if( root==null )

            return null;

        // root의 값의 찾는 Node 값이면, LinkedList의 앞부분에 추가하고 리턴

        LinkedList list = new LinkedList();

        if( root.getValue()==val ) {

            list.addFirst( root.getValue() );

            return list;

        }

        // root노드의 자식 노드들이 모두 null이면, null을 리턴

        if( root.getLeft()==null && root.getRight()==null )

        return null;

        // root의 왼쪽 Node 검색

        if( root.getLeft()!=null ) {

            list = findNode( root.getLeft(), val );

            // 리턴 값이 null이 아니면 현재 Node 값을 LinkedList 앞에 추가

            if( list!=null ) {

                list.addFirst( root.getValue() );

                return list;

            }

        }

        if( root.getRight()!=null  ) {

            list = findNode( root.getRight(), val );

            if( list!=null ) {

              list.addFirst( root.getValue() );

              return list;

            }

        }

        

        return null;

    }

   

    public static void findLCA( Node root, int p, int q ) {

        // root가 null 인지 확인

        if( root==null )
            System.out.println("Tree is empty");

        // 각 Node의 Path를 저장하기 위한 2개의 LinkedList 생성

        LinkedList pathP = new LinkedList();
        LinkedList pathQ = new LinkedList();

        pathP = findNode( root, p );
        pathQ = findNode( root, q );

        // LinkedList가 Null인지 확인

        if( pathP==null || pathQ==null ) {
        System.out.println( " Can't find LCA" );
        return;
        }

        // iteration을 위한 값 설정

        // 두 개의 LinkedList 중 size가 적은 것을 기준으로 iteration하면서 path 확인 

        int nSize = Math.min( pathP.size(), pathQ.size() );
        int LCA = -32767;
        int pVal = -32767;
        int qVal = -32767;
        int i=0;
       

        while( i

           pVal = pathP.poll();
           qVal = pathQ.poll();
           // Path 값이 동일하면 LCA 값 Update
           if( pVal==qVal )
               LCA = pVal;
           else
               break;
            i++;
        }
        if( LCA==-32767 )
        System.out.println( " Can't find LCA" );
        else
        System.out.println( " LCA is " + LCA );
    }