Array ( [0] => [1] => questions [2] => HackwithInfy-Previous-Questions [3] => Lowest-Common-Ancestor )
For the given array convert the array to BST and and find the lowest common factor for the give two nodes.
First line contains N representing no of elements in the array Second line contains N space separated lines which are elements of the array Third line contains 2 space separated integers which are two nodes of the Binary Tree.
Print the lowest common factor for the given two nodes.
7 20 8 4 22 12 10 14 8 14
8
5 1 5 7 4 2 1 2
1
9 1 2 3 4 5 6 8 2 1 4 5
4
Login to see Discussion
Step-i) Create a class Node with instances data of int type and left,right of Node type
Step-ii)create a default constructor which initializes left and right to null
Step-iii)create a constructor which accepts key as argument and assigns it to data
(this class is used to create a node of the tree)
Step-iv)create another class binary tree
Step-v)create a public method which return Node and takes root,node of Node type as arguments
Step-vi)if root is null assign node to root and return node
Step-vii)if data of root is less than data of node go to next step else go to ix
Step-viii)if right of root is null assign node to root right else call the insert method passing root.right and node as argument
Step-ix)if left of root is null assign node to root left else call the insert method passing root.left and node as argument
Step-x)return root
(now we are done with the insert method)
Step-xi)create a method lowest_comm_anc which accepts node,n1 and n2 as arguments and return Node
Step-xii)if node is equal to null return null
Step-xiii)if node.data is greater than both n1 and n2 return the value of lowest_comm_anc(node.left,n1,n2)
Step-xiv)if node.data is less than both n1 and n2 return the value of lowest_comm_anc(node.right,n1,n2)
Step-xv)return node
Step-xvi)in main method take the required inputs such as n,arr,n1 and n2
Step-xvii)pass the root ,n1 and n2 to the lowest_comm_anc method as arguments
Step-xviii)print the result
Time Complexity: O(h) where h is the height of the tree
Space Complexity:O(1) Ignoring the recursive stack space
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution