Find value K in given Complete Binary Tree with values indexed from 1 to N | Java program for the above approach ; Class containing left and right child of current node and key value ; Function to store the list of the directions ; While the root is not found ; If it is the right child of its parent ; Add right step ( 1 ) ; Add left step ( - 1 ) ; Repeat the same for its parent ; Reverse the steps list ; Return the steps ; Function to find if the key is present or not ; Get the steps to be followed ; Taking one step at a time ; Go left ; If left child does not exist return false ; Go right ; If right child does not exist return false ; If the entire array of steps has been successfully traversed ; Consider the following complete binary tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 ; Function Call
import java . util . * ; import java . io . * ; class Node { int data ; Node left , right ; public Node ( int item ) { data = item ; left = null ; right = null ; } } class Solution { public static ArrayList < Integer > findSteps ( Node root , int data ) { ArrayList < Integer > steps = new ArrayList < Integer > ( ) ; while ( data != 1 ) { if ( data / 2.0 > data / 2 ) { steps . add ( 1 ) ; } else { steps . add ( - 1 ) ; } int parent = data / 2 ; data = parent ; } Collections . reverse ( steps ) ; return steps ; } public static boolean findKey ( Node root , int data ) { ArrayList < Integer > steps = findSteps ( root , data ) ; for ( Integer cur_step : steps ) { if ( cur_step == - 1 ) { if ( root . left == null ) return false ; root = root . left ; } else { if ( root . right == null ) return false ; root = root . right ; } } return true ; } public static void main ( String [ ] args ) { 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 . left . left . left = new Node ( 8 ) ; root . left . left . right = new Node ( 9 ) ; root . left . right . left = new Node ( 10 ) ; System . out . println ( findKey ( root , 7 ) ) ; } }