// Input: nothing for the default test cases // or a list of integers. The list must be // exactly the right length to fill each // level (i.e. 1, 3, 7, 15, 31, 63.) // Created for this challenge: // https://www.sololearn.com/post/140168 // #* [[ CHALLENGE ]] *# // Largest_BST_In_a_Binary-Tree // 1) read picture // The first number is the root of the tree. // The next two are the children of the root. // The next four are the grandchildren of // the root. The next eight are the great- // grandchildren. // Drop the nodes with the -1 values. Search // the tree for the largest binary search // tree. Output the number of elements in // that sub-tree, the smallest value in the // sub-tree, the largest value in the sub- // tree, and index from the array for the // sub-tree root. // 2) inputs >>> // binaryTREE1 = [25, 18, 50, 19, 20, 35, 60, // -1, 15, 18, 25, 20, 40, 55, 70, -1, -1, -1, // -1, -1, -1, -1, -1, -1, 25, -1, -1, -1, -1, // -1, -1] // o/p>> [ 8, 20, 70, 3 ] // binaryTREE2 = [1, 4, 2, 3, 12, 3, 4, -1, -1, // 10, -1, 5, 6, -1, -1, -1, -1, -1, -1, -1, // 11, -1, -1, 7, 8, -1, -1, -1, -1] // o/p>> [ 5,3,12,2] // binaryTREE3 = [1, 10, 3, -1, 11, 5, 4, -1, // -1, -1, -1, 4, 6, -1, -1] //bo/p>> [3,4,6,6] // **** fill all null nodes with -1 upto last // to make tree look complete // **** ARRAY REPRESENTED AS THE LEVEL ORDER // TRAVERSAL OF THE BINARY TREE WHERE INDEX // STARTS FROM 1 AND CHILDREN OF i_th node // ARE 2*i ; 2*i+1 AND PARENT OF i_th node IS // floor( i/2 ) // . @@@@ any doubts? ask right // away @@@@ . // ## BONUS : try to make an O(n) algo where // n is length of array // Function to count the lines needed to // display the tree. fun levels(tree: List): Int { // Setup our initial size, zero our count, // and set the elements on the line to one. // While the size has at least one line // left, count it, subtract the elements // on this line from want is left, and // double the elements on the next line. var size = tree.size var count = 0 var power = 1 while (size > 0) { count++ size -= power power *= 2 } // while // If we were missing elements in our last // line, throw an exception. if (size < 0) throw IllegalArgumentException("Bad array!") return count } // levels // Function to display the input and tree // it forms. fun display(tree: List) { // Count the lines required for our tree. // This could cause an exception due to // the wrong number of elements. Display // our input array tree. Setup the // spacing needed per line. If our tree // fits in the lines we support, display // it. val lines = levels(tree) println("Input:\n$tree\n\nBecomes:") val spacing = listOf(0, 2, 6, 14, 30, 62) if (lines < spacing.size) { // Setup the array index and number of // elements on the line. For each line, // display it. For each value on the // line, display the beginning spacing, // display the value, increment to the // next element, and, if not the last // element, display the following // spacing. After all the values, // display the line finish and double // the elements for the next line. var index = 0 var power = 1 for (line in 1..lines) { for (value in 1..power) { print(" ".repeat(spacing[lines-line])) print("%4d".format(tree[index++])) if (value < power) print(" ".repeat(spacing[lines-line])) } // for println() power *= 2 } // for // Otherwise, state we can't handle // displaying the tree. } else println("Too big to display...") println() } // display // Function to make a list of left and right // indexes for each node. fun indexes(size: Int): List> { var index = -1 return List(size) { index += 2 Pair(index, index+1) } } // indexes // Function to process the tree. fun process(tree: List) { val index = indexes(tree.size) val counts = Array(tree.size) { 0 } var best = 0 // Function to find the maximum in our // sub-tree. Default to the sub-tree // root's value. While there is a // right side node, it's value is the // new maximum. fun max(): Int { var result = tree[best] var position = best do { val (left, right) = index[position] if (left < tree.size && tree[right] != -1) result = tree[right] else break position = right } while (true) return result } // max // Function to find the minimum in our // sub-tree. Default to the sub-tree // root's value. While there is a // left side node, it's value is the // new minimum. fun min(): Int { var result = tree[best] var position = best do { val (left, right) = index[position] if (left < tree.size && tree[left] != -1) result = tree[left] else break position = left } while (true) return result } // min // Display the input. For our elements // from our last to our first, find // best sub-tree. display(tree) for (position in tree.size-1 downTo 0) // If this node is non-existant, our // count is zero. if (tree[position] == -1) counts[position] = 0 // Otherwise, there is a node so figure // out it's sub-tree size. else { // Get the index to our left and right // nodes. If they are part of our tree, // figure out their size. val (left, right) = index[position] if (left < tree.size) { // If both left and right sub-tree // is valid, our left value is less // than our value, and either our // right value is greater than our // value or our right doesn't // exist, this sub-tree is valid // so our count is one plus the // counts of both our sub-trees. If // it is also the best we have seen // so far remember it. if (counts[left] >= 0 && counts[right] >= 0 && tree[left] < tree[position] && (tree[position] < tree[right] || tree[right] == -1)) { counts[position] = 1+counts[left]+ counts[right] if (counts[best] < counts[position]) best = position // Otherwise, this sub-tree isn't // valid so note that. } else counts[position] = -1 // Otherwise, this is an existing leaf // node so it's count is one. If it // is also the best we have seen so // far remember it. } else { counts[position] = 1 if (counts[best] < 1) best = position } // if } // if // Display our results. println("${counts[best]}, ${min()}, "+ "${max()}, ${best+1}") println() } // process // Main function to process this challenge. fun main(args: Array) { // Try reading the user's tree and process // it. An exception will be caused on // missing elements or non integer data. try { val array = readLine()!!.split(" ").map { it.toInt() } process(array) // On exception, complain and process our // default test cases. } catch (error: Throwable) { for (array in listOf(listOf(25, 18, 50, 19, 20, 35, 60, -1, 15, 18, 25, 20, 40, 55, 70, -1, -1, -1, -1, -1, -1, -1, -1, -1, 25, -1, -1, -1, -1, -1, -1), listOf(1, 4, 2, 3, 12, 3, 4, -1, -1, 10, -1, 5, 6, -1, -1, -1, -1, -1, -1, -1, 11, -1, -1, 7, 8, -1, -1, -1, -1, -1, -1), listOf(1, 10, 3, -1, 11, 5, 4, -1, -1, -1, -1, 4, 6, -1, -1), listOf(15, 10, 20, 7, 12, 17, 22, 1, 8, 11, 13, 16, 18, 21, 23))) process(array) } // try } // main

bst ch