Queries to find distance between two nodes of a Binary tree | Java program to find distance between two nodes for multiple queries ; A tree node structure ; Array to store level of each node ; Utility Function to store level of all nodes ; queue to hold tree node with level ; let root node be at level 0 ; Do level Order Traversal of tree ; Node p . first is on level p . second ; If left child exits , put it in queue with current_level + 1 ; If right child exists , put it in queue with current_level + 1 ; Stores Euler Tour ; index in Euler array ; Find Euler Tour ; store current node 's data ; If left node exists ; traverse left subtree ; store parent node 's data ; If right node exists ; traverse right subtree ; store parent node 's data ; checks for visited nodes ; Stores level of Euler Tour ; Stores indices of first occurrence of nodes in Euler tour ; Preprocessing Euler Tour for finding LCA ; If node is not visited before ; Add to first occurrence ; Mark it visited ; Stores values and positions ; Utility function to find minimum of pair type values ; Utility function to build segment tree ; Utility function to find LCA ; Function to return distance between two nodes n1 and n2 ; Maintain original Values ; Get First Occurrence of n1 ; Get First Occurrence of n2 ; Swap if low > high ; Get position of minimum value ; Extract value out of Euler tour ; return calculated distance ; Build Tree ; Store Levels ; Find L and H array ; Build segment Tree ; Driver Code ; Number of nodes ; Constructing tree given in the above figure ; Function to do all preprocessing
import java . io . * ; import java . util . * ; class GFG { static int MAX = 100001 ; static class Node { int data ; Node left , right ; Node ( int data ) { this . data = data ; this . left = this . right = null ; } } static class Pair < T , V > { T first ; V second ; Pair ( ) { } Pair ( T first , V second ) { this . first = first ; this . second = second ; } } static int [ ] level = new int [ MAX ] ; static void findLevels ( Node root ) { if ( root == null ) return ; Queue < Pair < Node , Integer > > q = new LinkedList < > ( ) ; q . add ( new Pair < Node , Integer > ( root , 0 ) ) ; Pair < Node , Integer > p = new Pair < Node , Integer > ( ) ; while ( ! q . isEmpty ( ) ) { p = q . poll ( ) ; level [ p . first . data ] = p . second ; if ( p . first . left != null ) q . add ( new Pair < Node , Integer > ( p . first . left , p . second + 1 ) ) ; if ( p . first . right != null ) q . add ( new Pair < Node , Integer > ( p . first . right , p . second + 1 ) ) ; } } static int [ ] Euler = new int [ MAX ] ; static int idx = 0 ; static void eulerTree ( Node root ) { Euler [ ++ idx ] = root . data ; if ( root . left != null ) { eulerTree ( root . left ) ; Euler [ ++ idx ] = root . data ; } if ( root . right != null ) { eulerTree ( root . right ) ; Euler [ ++ idx ] = root . data ; } } static int [ ] vis = new int [ MAX ] ; static int [ ] L = new int [ MAX ] ; static int [ ] H = new int [ MAX ] ; static void preprocessEuler ( int size ) { for ( int i = 1 ; i <= size ; i ++ ) { L [ i ] = level [ Euler [ i ] ] ; if ( vis [ Euler [ i ] ] == 0 ) { H [ Euler [ i ] ] = i ; vis [ Euler [ i ] ] = 1 ; } } } @ SuppressWarnings ( " unchecked " ) static Pair < Integer , Integer > [ ] seg = ( Pair < Integer , Integer > [ ] ) new Pair [ 4 * MAX ] ; static Pair < Integer , Integer > min ( Pair < Integer , Integer > a , Pair < Integer , Integer > b ) { if ( a . first <= b . first ) return a ; return b ; } static Pair < Integer , Integer > buildSegTree ( int low , int high , int pos ) { if ( low == high ) { seg [ pos ] . first = L [ low ] ; seg [ pos ] . second = low ; return seg [ pos ] ; } int mid = low + ( high - low ) / 2 ; buildSegTree ( low , mid , 2 * pos ) ; buildSegTree ( mid + 1 , high , 2 * pos + 1 ) ; seg [ pos ] = min ( seg [ 2 * pos ] , seg [ 2 * pos + 1 ] ) ; return seg [ pos ] ; } static Pair < Integer , Integer > LCA ( int qlow , int qhigh , int low , int high , int pos ) { if ( qlow <= low && qhigh >= high ) return seg [ pos ] ; if ( qlow > high qhigh < low ) return new Pair < Integer , Integer > ( Integer . MAX_VALUE , 0 ) ; int mid = low + ( high - low ) / 2 ; return min ( LCA ( qlow , qhigh , low , mid , 2 * pos ) , LCA ( qlow , qhigh , mid + 1 , high , 2 * pos + 1 ) ) ; } static int findDistance ( int n1 , int n2 , int size ) { int prevn1 = n1 , prevn2 = n2 ; n1 = H [ n1 ] ; n2 = H [ n2 ] ; if ( n2 < n1 ) { int temp = n1 ; n1 = n2 ; n2 = temp ; } int lca = LCA ( n1 , n2 , 1 , size , 1 ) . second ; lca = Euler [ lca ] ; return level [ prevn1 ] + level [ prevn2 ] - 2 * level [ lca ] ; } static void preProcessing ( Node root , int N ) { for ( int i = 0 ; i < 4 * MAX ; i ++ ) { seg [ i ] = new Pair < > ( ) ; } eulerTree ( root ) ; findLevels ( root ) ; preprocessEuler ( 2 * N - 1 ) ; buildSegTree ( 1 , 2 * N - 1 , 1 ) ; } public static void main ( String [ ] args ) { int N = 8 ; Node root = new Node ( 1 ) ; root . left = new Node ( 2 ) ; root . right = new Node ( 3 ) ; root . left . left = new Node ( 4 ) ; root . left . right = new Node ( 5 ) ; root . right . left = new Node ( 6 ) ; root . right . right = new Node ( 7 ) ; root . right . left . right = new Node ( 8 ) ; preProcessing ( root , N ) ; System . out . println ( " Dist ( 4 , ▁ 5 ) ▁ = ▁ " + findDistance ( 4 , 5 , 2 * N - 1 ) ) ; System . out . println ( " Dist ( 4 , ▁ 6 ) ▁ = ▁ " + findDistance ( 4 , 6 , 2 * N - 1 ) ) ; System . out . println ( " Dist ( 3 , ▁ 4 ) ▁ = ▁ " + findDistance ( 3 , 4 , 2 * N - 1 ) ) ; System . out . println ( " Dist ( 2 , ▁ 4 ) ▁ = ▁ " + findDistance ( 2 , 4 , 2 * N - 1 ) ) ; System . out . println ( " Dist ( 8 , ▁ 5 ) ▁ = ▁ " + findDistance ( 8 , 5 , 2 * N - 1 ) ) ; } }